Phase estimation ยท Circuits
Quantum Fourier transform
Theorem statement
Let $n\geq 1$ and $N=2^n$. There is an $n$-qubit quantum circuit using $n$ Hadamard gates, $n(n-1)/2$ controlled-phase gates, and $\lfloor n/2\rfloor$ SWAP gates whose unitary matrix is $\mathtt{QFT}_{N}$ satisfying
$$
\mathtt{QFT}_{N}\ket{j}
=
\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk}\ket{k}.
$$
- $\mathtt{QFT}_{N}$
- Quantum Fourier transform over N computational-basis states.
- $\omega_N$
- Primitive N-th root of unity used in the Fourier phase.
Sources
- Quantum Computing: Lecture Notes
Ronald de Wolf, 2019
- Quantum Algorithms Revisited
Richard Cleve, Artur Ekert, Chiara Macchiavello, Michele Mosca, 1998
- Quantum Computation and Quantum Information
Michael A. Nielsen, Isaac L. Chuang, 2010
Lean context
- Import
QuantumAlg.Primitives.QFT- Lean declaration
QuantumAlg.QuantumFourierTransform.main
Copy a short prompt with the import, theorem name, citations, and public source link.