Skip to content

Quantum Fourier transform

Rough overview (in words)

The quantum Fourier transform (QFT) is a quantum version of the discrete Fourier transform (DFT) and takes quantum states to their Fourier transformed version.

Rough overview (in math)

The QFT is a quantum circuit that takes pure \(N\)-dimensional quantum states \(\ket{x}=\sum_{i=0}^{N-1}x_i\ket{i}\) to pure quantum states \(\ket{y}=\sum_{i=0}^{N-1}y_i\ket{i}\) with the Fourier transformed amplitudes

\[\begin{align} \label{eq:Fourier} y_k=\frac{1}{\sqrt{N}}\sum_{l=0}^{N-1}x_l\exp(2\pi ikl/N)\quad\text{for }k=0,\cdots,N-1. \end{align}\]

Dominant resource cost (gates/qubits)

The space cost is \(\mathcal{O}\left( \log(N) \right)\) qubits and the quantum complexity of the textbook algorithm is \(\mathcal{O}\left( \log^2(N) \right)\). In terms of Hadamard gates, swap gates, and controlled phase shift gates \(\ket{0}\bra{0}\otimes I + \ket{1}\bra{1}\otimes R_\ell\) with

\[\begin{align} R_\ell=\begin{pmatrix} 1 & 0\\ 0 & \exp\left(2\pi i2^{-\ell}\right)\end{pmatrix}\,, \end{align}\]

the quantum circuit looks as follows [1, Fig. 5.1], where \(N=2^n\): image The swap gates at the end of the circuit are required to reverse the order of the output bits. The complexity can be improved to

\[\begin{align} \mathcal{O}\left( \log(N)\log\left(\log(N)\epsilon^{-1}\right)+\log^2\left(\epsilon^{-1}\right) \right) \end{align}\]

when only asking for \(\epsilon\)-approximate solutions [2]. Finite constants and compilation cost for fault-tolerant quantum architectures are also discussed in the literature. For example [3] gives an implementation with \(\mathcal{O}\left( \log(N)\log\log(N) \right)\) \(T\)-gates and estimates finite \(T\)-gate costs for different instance sizes.

Caveats

  • The QFT does not achieve the same task as the classical DFT that takes vectors \((x_0,\cdots,x_{N-1})\in\mathbb{C}^N\) to vectors \((y_0,\cdots,y_{N-1})\in\mathbb{C}^N\) with \(y_k\) defined as in Eq. \(\eqref{eq:Fourier}\). The DFT can be implemented via the fast Fourier transform in classical complexity \(\mathcal{O}\left( N\log(N) \right)\), which is exponentially more costly than the quantum complexity \(\mathcal{O}\left( \log^2(N) \right)\) of the QFT. However, for the QFT to achieve the same task as the DFT, pure state quantum tomography would be required to read out and learn the Fourier-transformed amplitudes, which destroys any quantum speedup for the DFT.
  • When QFT is employed in use cases, e.g., for factoring, one has to be careful in finite size instances when counting resources [4], and for this a semi-classical version of the QFT can be more quantum resource efficient [5].

Example use cases

  • Even though the QFT does not speedup the DFT, QFT is used as a subroutine in more involved quantum routines with large quantum speedup. Examples include quantum algorithms for the discrete logarithm problem, the hidden subgroup problem, the factoring problem, to name a few. QFT can be seen as the crucial quantum ingredient that allows for a super-polynomial end-to-end quantum speedup for these problems. We discuss this in the context of quantum cryptanalysis.
  • The QFT appears in the standard circuit for quantum phase estimation, where it is used to convert accrued phase estimation into a binary value that can be read out.
  • The QFT is used for switching between the position and momentum bases in grid-based simulations of quantum chemistry [6] or quantum field theories [7].

Further reading

  • Textbook reference [1, Chapter 5]
  • Wikipedia article Quantum Fourier transform
  • The quantum Fourier transform can be generalized to other groups. The version presented above is for the group \(\mathbb{Z}/(2^n\mathbb{Z})\). Its implementation for other abelian groups as well as non-abelian groups is discussed in [8] and the references therein.

Bibliography

  1. Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000. doi:10.1017/CBO9780511976667.

  2. L. Hales and S. Hallgren. An improved quantum fourier transform algorithm and applications. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), 515–525. 2000. doi:10.1109/SFCS.2000.892139.

  3. Yunseong Nam, Yuan Su, and Dmitri Maslov. Approximate quantum fourier transform with \(o(n \log (n))\) t gates. npj Quantum Information, 6(1):26, 2020. arXiv: https://arxiv.org/abs/1803.04933. URL: https://doi.org/10.1038/s41534-020-0257-5, doi:10.1038/s41534-020-0257-5.

  4. John A. Smolin, Graeme Smith, and Alexander Vargo. Oversimplifying quantum factoring. Nature, 499(7457):163–165, 2013. URL: https://doi.org/10.1038/nature12290, doi:10.1038/nature12290.

  5. Robert B. Griffiths and Chi-Sheng Niu. Semiclassical fourier transform for quantum computation. Physical Review Letters, 76(17):3228, 1996. arXiv: https://arxiv.org/abs/quant-ph/9511007. doi:10.1103/PhysRevLett.76.3228.

  6. Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán Aspuru-Guzik. Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences, 105(48):18681–18686, 2008. arXiv: https://arxiv.org/abs/0801.2986. URL: https://www.pnas.org/doi/abs/10.1073/pnas.0808245105, arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.0808245105, doi:10.1073/pnas.0808245105.

  7. Stephen P. Jordan, Keith S. M. Lee, and John Preskill. Quantum algorithms for quantum field theories. Science, 336(6085):1130–1133, 2012. arXiv: https://arxiv.org/abs/1111.3633. URL: https://www.science.org/doi/abs/10.1126/science.1217069, arXiv:https://www.science.org/doi/pdf/10.1126/science.1217069, doi:10.1126/science.1217069.

  8. Andrew M. Childs and Wim van Dam. Quantum algorithms for algebraic problems. Reviews of Modern Physics, 82:1–52, 1 2010. arXiv: https://arxiv.org/abs/0812.0380. URL: https://link.aps.org/doi/10.1103/RevModPhys.82.1, doi:10.1103/RevModPhys.82.1.