Quantum Fourier transform

In quantum computing, the quantum Fourier transform (for short: QFT) 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 on $2^{n}$ amplitudes can be implemented as a quantum circuit consisting of only $O(n^{2})$ Hadamard gates and controlled phase shift gates, where $n$ is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes $O(n2^{n})$ gates (where $n$ is the number of bits), which is exponentially more than $O(n^{2})$. 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 (as of late 2000) require only $O(n\log n)$ gates to achieve an efficient approximation.

Definition

The quantum Fourier transform is the classical discrete Fourier transform applied to the vector of amplitudes of a quantum state, where we usually consider vectors of length $N:=2^{n}$. The classical Fourier transform acts on a vector $(x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}$ and maps it to the vector $(y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}$ according to the formula

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{jk},\quad k=0,1,2,\ldots ,N-1,$

where $\omega _{n}=e^{\frac {2\pi i}{N}}$ is an N^th root of unity.

Similarly, the quantum Fourier transform acts on a quantum state $|x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle$ and maps it to a quantum state $\sum _{i=0}^{N-1}y_{i}|i\rangle$ according to the formula:

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{jk},\quad k=0,1,2,\ldots ,N-1,$

with $\omega _{n}$ defined as above. Since $\omega _{n}$ is a rotation, the inverse quantum Fourier transform acts similarly but with

$y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{n}^{-jk}$

In case that $|x\rangle$ is a basis state, the quantum Fourier Transform can also be expressed as the map

$QFT:|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{n}^{xk}|k\rangle .$

Equivalently, the quantum Fourier transform can be viewed as a unitary matrix (or a quantum gate, similar to a boolean logic gate for classical computers) acting on quantum state vectors, where the unitary matrix $F_{N}$ is given by

$F_{N}={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega _{n}&\omega _{n}^{2}&\omega _{n}^{3}&\cdots &\omega _{n}^{N-1}\\1&\omega _{n}^{2}&\omega _{n}^{4}&\omega _{n}^{6}&\cdots &\omega _{n}^{2(N-1)}\\1&\omega _{n}^{3}&\omega _{n}^{6}&\omega _{n}^{9}&\cdots &\omega _{n}^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &&\vdots \\1&\omega _{n}^{N-1}&\omega _{n}^{2(N-1)}&\omega _{n}^{3(N-1)}&\cdots &\omega _{n}^{(N-1)(N-1)}\end{bmatrix}}.$

Since $N:=2^{n}$ and $\omega _{n}:=e^{\frac {2\pi i}{2^{n}}}$ is a primitive N^th root of unity, we get, for example, in the case of $N=4=2^{2}$ and phase $\omega _{2}=i$ the transformation matrix

$F_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}.$

See also: Generalizations of Pauli matrices § Construction: The clock and shift matrices

Properties

Unitarity

Quantum circuit simulations of a 2-qubit QFT using Q-Kit

Most of the properties of the quantum Fourier transform follow from the fact that it is a unitary transformation. This can be checked by performing matrix multiplication and ensuring that the relation $FF^{\dagger }=F^{\dagger }F=I$ holds, where $F^{\dagger }$ is the Hermitian adjoint of $F$. Alternately, one can check that orthogonal vectors of norm 1 get mapped to orthogonal vectors of norm 1.

From the unitary property it follows that the inverse of the quantum Fourier transform is the Hermitian adjoint of the Fourier matrix, thus $F^{-1}=F^{\dagger }$. Since there is an efficient quantum circuit implementing the quantum Fourier transform, the circuit can be run in reverse to perform the inverse quantum Fourier transform. Thus both transforms can be efficiently performed on a quantum computer.

Quantum circuit simulations of both possible implementations of a 2-qubit QFT, using $F$ and $F^{-1}$ are shown to give the same results using Q-Kit, a graphical quantum circuit simulator. Moreover, starting from the matrix operators for quantum gates, the circuits are built intuitively leading to the QFT matrix.

Circuit implementation

The quantum gates used in the circuit are the Hadamard gate and the controlled phase gate $R_{m}$, here in terms of

$H:={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad and\qquad R_{m}:={\begin{pmatrix}1&0\\0&\omega _{m}\end{pmatrix}}$

with $\omega _{m}:=e^{\frac {2\pi i}{2^{m}}}$ the $2^{m}$-th root of unity.

All quantum operations must be linear, so it suffices to describe the function on each one of the basis states and let the mixed states be defined by linearity. This is in contrast to how Fourier transforms are usually described. We normally describe Fourier transforms in terms of how the components of the results are calculated on an arbitrary input. This is how you would calculate the path integral or show BQP is in PP. But it is much simpler here (and in many cases) to just explain what happens to a specific arbitrary basis state, and the total result can be found by linearity.

The quantum Fourier transform can be approximately implemented for any N; however, the implementation for the case where N is a power of 2 is much simpler. As already stated, we assume $N=2^{n}$. We have the orthonormal basis consisting of the vectors

$|0\rangle ,\ldots ,|2^{n}-1\rangle .$

The basis states enumerate all the possible states of the qubits:

$|x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_{n}\rangle$

where, with tensor product notation $\otimes$, $|x_{j}\rangle$ indicates that qubit $j$ is in state $x_{j}$, with $x_{j}$ either 0 or 1. By convention, the basis state index $x$ orders the possible states of the qubits lexicographically, i.e., by converting from binary to decimal in this way:

$x=x_{1}2^{n-1}+x_{2}2^{n-2}+\cdots +x_{n}2^{0}.\quad$

It is also useful to borrow fractional binary notation:

$[0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.$

For instance, $[0.x_{1}]={\frac {x_{1}}{2}}$ and $[0.x_{1}x_{2}]={\frac {x_{1}}{2}}+{\frac {x_{2}}{2^{2}}}.$

With this notation, the action of the quantum Fourier transform can be expressed in a compact manner:

$QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{n}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{n-1}x_{n}]}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right)$

or

$QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +\omega _{1}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +\omega _{n}^{x}|1\rangle \right).$

This can be seen by rewriting the formula for the Fourier transform in the binary expansion

$QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\sum _{k=0}^{2^{n}-1}e^{2\pi ik[0.x_{1}x_{2}\ldots x_{n}]}|k\rangle$

$={\frac {1}{\sqrt {N}}}\sum _{\{k_{0},k_{1},...k_{n-1}\}\in \{0,1\}^{n}}e^{2\pi i\sum _{j=1}^{n}k_{n-j}2^{j-1}[0.x_{1}x_{2}\ldots x_{n}]}|k_{0}k_{1}\ldots k_{n-1}\rangle$

$={\frac {1}{\sqrt {N}}}\sum _{\{k_{0},k_{1},...k_{n-1}\}\in \{0,1\}^{n}}\prod _{j=1}^{n}e^{2\pi ik_{n-j}[0.x_{j}x_{j+1}\ldots x_{n}]}|k_{0}k_{1}\ldots k_{n-1}\rangle$

$={\frac {1}{\sqrt {N}}}(|0\rangle +e^{2\pi i[0.x_{n}]}|1\rangle )\sum _{\{k_{1},...k_{n-1}\}\in \{0,1\}^{n-1}}\prod _{j=1}^{n-1}e^{2\pi ik_{n-j}[0.x_{j}x_{j+1}\ldots x_{n}]}|k_{1}\ldots k_{n-1}\rangle$

$={\frac {1}{\sqrt {N}}}\prod _{j=1}^{n}(|0\rangle +e^{2\pi i[0.x_{j}x_{j+1}\ldots x_{n}]}|1\rangle )$

As can be seen, the output qubit 1 is in a superposition of state $|0\rangle$ and $e^{2\pi i\,[0.x_{1}...x_{n}]}|1\rangle$, and so on for the other qubits (take a second look at the sketch of the circuit above).

In other words, the discrete Fourier transform, an operation on n-qubits, can be factored into the tensor product of n single-qubit operations, suggesting it is easily represented as a quantum circuit (ignoring the reverse order of outputs). In fact, each of those single-qubit operations can be implemented efficiently using a Hadamard gate and controlled phase gates. The first term requires one Hadamard gate and (n-1) controlled phase gates, the next one requires a Hadamard gate and (n-2) controlled phase gate, and each following term requires one fewer controlled phase gate. Summing up the number of gates gives $n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})$ gates, which is quadratic polynomial in the number of qubits.

Example

Consider the quantum Fourier transform on 3 qubits. It is the following transformation:

$QFT:|x\rangle \mapsto {\frac {1}{\sqrt {2^{3}}}}\sum _{k=0}^{2^{3}-1}\omega _{3}^{xk}|k\rangle ,$

where $\omega _{3}$ is a primitive eighth root of unity satisfying $\omega _{3}^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1$ (since $N=2^{3}=8$).

For short, setting $\omega :=\omega _{3}$, the matrix representation of this transformation on 3 qubits is

$F_{2^{3}}={\frac {1}{\sqrt {2^{3}}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\omega ^{8}&\omega ^{10}&\omega ^{12}&\omega ^{14}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\omega ^{12}&\omega ^{15}&\omega ^{18}&\omega ^{21}\\1&\omega ^{4}&\omega ^{8}&\omega ^{12}&\omega ^{16}&\omega ^{20}&\omega ^{24}&\omega ^{28}\\1&\omega ^{5}&\omega ^{10}&\omega ^{15}&\omega ^{20}&\omega ^{25}&\omega ^{30}&\omega ^{35}\\1&\omega ^{6}&\omega ^{12}&\omega ^{18}&\omega ^{24}&\omega ^{30}&\omega ^{36}&\omega ^{42}\\1&\omega ^{7}&\omega ^{14}&\omega ^{21}&\omega ^{28}&\omega ^{35}&\omega ^{42}&\omega ^{49}\\\end{bmatrix}}={\frac {1}{\sqrt {2^{3}}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&1&\omega ^{2}&\omega ^{4}&\omega ^{6}\\1&\omega ^{3}&\omega ^{6}&\omega &\omega ^{4}&\omega ^{7}&\omega ^{2}&\omega ^{5}\\1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}\\1&\omega ^{5}&\omega ^{2}&\omega ^{7}&\omega ^{4}&\omega &\omega ^{6}&\omega ^{3}\\1&\omega ^{6}&\omega ^{4}&\omega ^{2}&1&\omega ^{6}&\omega ^{4}&\omega ^{2}\\1&\omega ^{7}&\omega ^{6}&\omega ^{5}&\omega ^{4}&\omega ^{3}&\omega ^{2}&\omega \\\end{bmatrix}}.$

It could be simplified further by using $\omega ^{4}=-1$, $\omega ^{2}=i$ and $\omega ^{6}=-i$

and then even more given that $\omega ^{5}=-\omega$, $\omega ^{3}=i\omega$ and $\omega ^{7}=-i\omega$.

The 3-qubit quantum Fourier transform can be rewritten as:

$QFT(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}x_{3}]}|1\rangle \right)$

or

$QFT(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +\omega _{1}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{3}^{x}|1\rangle \right).$

In case that we use the circuit we obtain the factorization in reverse order, namely

$|x_{1},x_{2},x_{3}\rangle \longmapsto {\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +\omega _{3}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{2}^{x}|1\rangle \right)\otimes \left(|0\rangle +\omega _{1}^{x}|1\rangle \right).$

In the following sketch we have the respective circuit for $n:=3$ (with wrong order of output qubits with respect to the proper QFT).

Possible implementations of a 3-qubit QFT circuit using Q-Kit

As calculated above, the number of gates used is $n(n+1)/2$ which is equal to $6$, for $n=3$.

Moreover, the following link shows the situation for 1-, 2- and 3-qubit case: Sketch and simulator for 1-, 2- and 3-qubit QFT

Simulations of up to 20-qubit QFTs can be done on Q-Kit, a quantum circuit simulator with a graphical interface. Figure shows 2 different implementations of a 3-qubit QFT are equivalent.

References

• K. R. Parthasarathy, Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, June 2001)
• John Preskill, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, September 1998)

External links

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm
• Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform
• Q-Kit: Graphical Quantum Circuit Simulator
• Quirk online life quantum fourier transform