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:
“But how is one to make a scientist understand that there is something unalterably deranged about differential calculus, quantum theory, or the obscene and so inanely liturgical ordeals of the precession of the equinoxes.”
—Antonin Artaud (1896–1948)
“Government ... thought [it] could transform the country through massive national programs, but often the programs did not work. Too often they only made things worse. In our rush to accomplish great deeds quickly, we trampled on sound principles of restraint and endangered the rights of individuals.”
—Gerald R. Ford (b. 1913)