In quantum computing, the quantum Fourier transform is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem.
The quantum Fourier transform can be performed efficiently on a quantum computer, with a particular decomposition into a product of simpler unitary matrices. Using a simple decomposition, the discrete Fourier transform can be implemented as a quantum circuit consisting of only Hadamard gates and controlled phase shift gates, where is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes gates (where is the number of bits), which is exponentially more than . However, the quantum Fourier transform acts on a quantum state, whereas the classical Fourier transform acts on a vector, so not every task that uses the classical Fourier transform can take advantage of this exponential speedup.
The best quantum Fourier transform algorithms known today require only gates to achieve an efficient approximation.
Read more about Quantum Fourier Transform: Definition, Circuit Implementation, Example
Famous quotes containing the words quantum and/or transform:
“The receipt to make a speaker, and an applauded one too, is short and easy.—Take of common sense quantum sufficit, add a little application to the rules and orders of the House, throw obvious thoughts in a new light, and make up the whole with a large quantity of purity, correctness, and elegancy of style.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“The lullaby is the spell whereby the mother attempts to transform herself back from an ogre to a saint.”
—James Fenton (b. 1949)