Categories: Algorithms, Quantum information.

Quantum Fourier transform

The quantum Fourier transform (QFT) is a quantum counterpart of the classical discrete Fourier transform. It is defined like so, where x\Ket{x} is an nn-qubit computational basis state x1xn\Ket{x_1} \cdots \Ket{x_n}, and ωN\omega_N is an NNth complex root of unity ωNN=1\omega_N^N = 1 with N=2nN = 2^n:

x1Nk=0N1ωNxkk\begin{aligned} \boxed{ \Ket{x} \:\to\: \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \Ket{k} } \end{aligned}

Note that x\Ket{x} and k\Ket{k} refer to the same basis set; we use these names to clarify which “space” we are considering. Furthermore, note the sign of the exponent of ωN\omega_N, which is the opposite of the classical DFT convention. In other words, the forward QFT corresponds to the inverse DFT.

The inverse quantum Fourier transform (iQFT) has a different sign in the exponent:

k1Nx=0N1ωNxkx\begin{aligned} \boxed{ \Ket{k} \:\to\: \frac{1}{\sqrt{N}} \sum_{x = 0}^{N - 1} \omega_N^{-xk} \Ket{x} } \end{aligned}

The above definitions of the QFT and iQFT describe the effect on a single basis vector x\Ket{x}, so the effect on an abitrary superposition follows from linearity, e.g. for the QFT:

x=0N1cxxx=0N1cx(1Nk=0N1ωNxkk)\begin{aligned} \sum_{x = 0}^{N - 1} c_x \Ket{x} \:\to\: \sum_{x = 0}^{N - 1} c_x \bigg( \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \Ket{k} \bigg) \end{aligned}

Classically, such a double sum takes O(N2)=O(22n)\mathcal{O}(N^2) = \mathcal{O}(2^{2n}) time to evaluate naively, with a potential improvement to O(NlogN)=O(n2n)\mathcal{O}(N \log{N}) = \mathcal{O}(n 2^n) for smarter algorithms. Quantum computers can do a QFT in O(log2(N))=O(n2)\mathcal{O}(\log^2(N)) = \mathcal{O}(n^2) time, and approximate it in O(nlogn)\mathcal{O}(n \log{n}) time.

To find out how, we look at the forward QFT, which maps a basis state x\Ket{x} to another state x~\Ket{\tilde{x}}:

xx~=1Nk=0N1ωNxkk=1Nk=0N1exp ⁣(i2πxkN)k\begin{aligned} \Ket{x} \:\to\: \Ket{\tilde{x}} = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \omega_N^{xk} \Ket{k} = \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} \exp\!\bigg( \frac{i 2 \pi x k}{N} \bigg) \Ket{k} \end{aligned}

We can decompose kk into its binary representation k12n1+k22n2+...+kn20k_1 2^{n-1} + k_2 2^{n-2} + ... + k_n 2^{0}:

x~=12nk=02n1exp ⁣(i2πx2nj=1nkj2nj)k=12nk=02n1exp ⁣(i2πxj=1nkj2j)k\begin{aligned} \Ket{\tilde{x}} &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \exp\!\bigg( \frac{i 2 \pi x}{2^n} \sum_{j = 1}^{n} k_j 2^{n-j} \bigg) \Ket{k} \\ &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \exp\!\bigg( i 2 \pi x \sum_{j = 1}^{n} \frac{k_j}{2^j} \bigg) \Ket{k} \end{aligned}

Expanding the exponential-of-a-sum into a product-of-exponentials then yields:

x~=12nk=02n1j=1nexp ⁣(i2πxkj2j)k\begin{aligned} \Ket{\tilde{x}} &= \frac{1}{\sqrt{2^n}} \sum_{k = 0}^{2^n - 1} \prod_{j = 1}^{n} \exp\!\bigg( i 2 \pi x \frac{k_j}{2^j} \bigg) \Ket{k} \end{aligned}

If kj=0k_j = 0, the exponential is zero. We can thus separate this state into its individual qubits:

x~=j=1n12(0+exp ⁣(i2πx2j)1)\begin{aligned} \Ket{\tilde{x}} &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \Ket{0} + \exp\!\Big( \frac{i 2 \pi x}{2^j} \Big) \Ket{1} \bigg) \end{aligned}

Next, we use the trick from before: decompose xx as x12n1+x22n2+...+xn20x_1 2^{n-1} + x_2 2^{n-2} + ... + x_n 2^{0}:

x~=j=1n12(0+exp ⁣(i2πr=1nxr2nrj)1)\begin{aligned} \Ket{\tilde{x}} &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \sum_{r = 1}^{n} x_r 2^{n-r-j} \Big) \Ket{1} \bigg) \end{aligned}

The factor 2nrj2^{n-r-j} may be smaller or bigger than 11, so it is convenient for us to use the following notation for non-integer binary numbers. Note the decimal point in the middle:

[]=r=1nar2dr\begin{aligned} \left[ a_1 \cdots a_{d} \:.\: a_{d+1} \cdots a_{n} \right] = \sum_{r = 1}^{n} a_r 2^{d - r} \end{aligned}

In the above QFT state, the position of the decimal point is d=njd = n - j, so we write it as:

x~=j=1n12(0+exp ⁣(i2π[x1xnj.xnj+1xn])1)\begin{aligned} \Ket{\tilde{x}} &= \bigotimes_{j = 1}^{n} \frac{1}{\sqrt{2}} \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \big[ x_1 \cdots x_{n-j} \:.\: x_{n-j+1} \cdots x_n \big] \Big) \Ket{1} \bigg) \end{aligned}

Because exp(i2πm)=1\exp(i 2 \pi m) = 1 for all integers mm, we can discard bits before the decimal point:

x~=12nj=1n(0+exp ⁣(i2π[0.xnj+1xn])1)=12n(0+exp ⁣(i2π[0.xn])1)(0+exp ⁣(i2π[0.xn1xn])1)\begin{aligned} \Ket{\tilde{x}} &= \frac{1}{\sqrt{2^n}} \bigotimes_{j = 1}^{n} \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \big[ 0\:.\: x_{n-j+1} \cdots x_n \big] \Big) \Ket{1} \bigg) \\ &= \frac{1}{\sqrt{2^n}} \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \big[ 0. x_n \big] \Big) \Ket{1} \bigg) \otimes \bigg( \Ket{0} + \exp\!\Big( i 2 \pi \big[ 0. x_{n-1} x_n \big] \Big) \Ket{1} \bigg) \otimes \cdots \end{aligned}

Furthermore, each exponential can be factorized, with every factor containing one bit of xx:

exp ⁣(i2π[0.xnj+1xn])=exp ⁣(i2πxnj+12)exp ⁣(i2πxn2j)\begin{aligned} \exp\!\Big( i 2 \pi \big[ 0\:.\: x_{n-j+1} \cdots x_n \big] \Big) = \exp\!\Big( i 2 \pi \frac{x_{n-j+1}}{2} \Big) \cdots \exp\!\Big( i 2 \pi \frac{x_{n}}{2^{j}} \Big) \end{aligned}

This suggests a way to implement the QFT using quantum gates in a circuit. If the jjth qubit is in +=(0+1)/2\Ket{+} = (\Ket{0} + \Ket{1})/\sqrt{2}, then for each bit xnj+rx_{n-j+r} where r{1,...,j}r \in \{1, ..., j\}:

The full QFT algorithm therefore proceeds as follows, for the (n ⁣ ⁣j ⁣+ ⁣1)(n\!-\!j\!+\!1)‘th input xnj+1\Ket{x_{n-j+1}}:

  1. Apply the Hadamard gate HH. If xnj+1=0x_{n-j+1} = 0, this puts the qubit in +\Ket{+}. If xnj+1=1x_{n-j+1} = 1, this puts the qubit in +\Ket{+}, and then adds a phase π\pi, yielding \Ket{-}.
  2. Apply the phase shift gate RϕR_{\phi} controlled by xnj+2x_{n-j+2}, with angle ϕ=2π/22\phi = 2 \pi / 2^{2}.
  3. Apply RϕR_{\phi} controlled by xnj+3x_{n-j+3}, with angle ϕ=2π/23\phi = 2 \pi / 2^{3}
  4. And so on, until the nnth bit xnx_n is reached, and used to control RϕR_\phi with ϕ=2π/2j\phi = 2 \pi / 2^{j}.

And so on, for each j{1,...,n}j \in \{1, ..., n\}, and we reach the above expression for x~\Ket{\tilde{x}}. We started from the (n ⁣ ⁣j ⁣+ ⁣1)(n\!-\!j\!+\!1)‘th input qubit, i.e. we read the input in reverse order. Therefore all the qubits need to be swapped back to front, either before or after the above algorithm is run.

The quantum circuit to execute the mentioned steps is illustrated below, excluding the swapping part to get the right order. Here, RmR_m means RϕR_\phi with ϕ=2π/2m\phi = 2 \pi / 2^m:

QFT circuit, without final swap

Again, note how the inputs xj\Ket{x_j} and outputs kj\Ket{k_j} are in the opposite order. The complete circuit, including the swapping at the end, therefore looks like this:

QFT circuit, including final swap

For each of the nn qubits, O(n)\mathcal{O}(n) gates are applied, so overall the QFT algorithm is O(n2)\mathcal{O}(n^2).


  1. J.S. Neergaard-Nielsen, Quantum information: lectures notes, 2021, unpublished.
  2. S. Aaronson, Introduction to quantum information science: lecture notes, 2018, unpublished.