Inquantum computing, thequantum Fourier transform (QFT) is alinear transformation onquantum bits, and is the quantum analogue of thediscrete Fourier transform. The quantum Fourier transform is a part of manyquantum algorithms, notablyShor's algorithm for factoring and computing thediscrete logarithm, thequantum phase estimation algorithm for estimating theeigenvalues of aunitary operator, and algorithms for thehidden subgroup problem. The quantum Fourier transform was discovered byDon Coppersmith.^[1] With small modifications to the QFT, it can also be used for performing fastinteger arithmetic operations such as addition and multiplication.^[2][3][4]

The quantum Fourier transform can be performed efficiently on a quantum computer with a decomposition into the product of simplerunitary matrices. The discrete Fourier transform on${\displaystyle 2^n}$ amplitudes can be implemented as aquantum circuit consisting of only${\displaystyle O(n^2)}$Hadamard gates andcontrolledphase shift gates, where${\displaystyle n}$ is the number of qubits.^[5] This can be compared with the classical discrete Fourier transform, which takes${\displaystyle O(n{2}^n)}$ gates (where${\displaystyle n}$ is the number of bits), which is exponentially more than${\displaystyle O(n^2)}$.

The quantum Fourier transform acts on aquantum state vector (aquantum register), and the classicaldiscrete Fourier transform acts on a vector. Both types of vectors can be written as lists of complex numbers. In the classical case, the vector can be represented with e.g. an array offloating-point numbers, and in the quantum case it is a sequence ofprobability amplitudes for all the possible outcomes uponmeasurement (the outcomes are thebasis states, oreigenstates). Because measurementcollapses the quantum state to a single basis state, not every task that uses the classical Fourier transform can take advantage of the quantum Fourier transform's exponential speedup.

The best quantum Fourier transform algorithms known (as of late 2000) require only${\displaystyle O(n\log n)}$ gates to achieve an efficient approximation, provided that acontrolledphase gate is implemented as a native operation.^[6]

The quantum Fourier transform is the classical discrete Fourier transform applied to the vector of amplitudes of a quantum state, which has length${\displaystyle N=2^n}$ if it is applied to a register of${\displaystyle n}$ qubits.

Theclassical Fourier transform acts on avector${\displaystyle (x_0,x_1,\dots ,x_{N-1})\in {\mathbb{C}}^N}$ and maps it to the vector${\displaystyle (y_0,y_1,\dots ,y_{N-1})\in {\mathbb{C}}^N}$ according to the formula

${\displaystyle y_k=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}{x}_j{\omega }_N^{-jk},k=0,1,2,\dots ,N-1,}$

where${\displaystyle {\omega }_N=e^{\frac{2\pi i}{N}}}$ is anN-throot of unity.

Similarly, thequantum Fourier transform acts on a quantum state$|x⟩=\sum _{j=0}^{N-1}{x}_j|j⟩$ and maps it to a quantum state$\sum _{j=0}^{N-1}{y}_j|j⟩$ according to the formula

${\displaystyle y_k=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}{x}_j{\omega }_N^{jk},k=0,1,2,\dots ,N-1.}$

(Conventions for the sign of the phase factor exponent vary; here the quantum Fourier transform has the same effect as the inverse discrete Fourier transform, and conversely.)

Since${\displaystyle {\omega }_N^l}$ is a rotation, theinverse quantum Fourier transform acts similarly but with

${\displaystyle x_j=\frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{y}_k{\omega }_N^{-jk},j=0,1,2,\dots ,N-1,}$

In case that${\displaystyle |x⟩}$ is a basis state, the quantum Fourier transform can also be expressed as the map

${\displaystyle \mathrm{QFT}:|x⟩\mapsto \frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{\omega }_N^{xk}|k⟩.}$

Equivalently, the quantum Fourier transform can be viewed as aunitary matrix (orquantum gate) acting on quantum state vectors, where the unitary matrix${\displaystyle F_N}$ is theDFT matrix

where${\displaystyle \omega ={\omega }_N}$. For example, in the case of${\displaystyle N=4=2^2}$ and phase${\displaystyle \omega =i}$ the transformation matrix is

Most of the properties of the quantum Fourier transform follow from the fact that it is aunitary transformation. This can be checked by performingmatrix multiplication and ensuring that the relation${\displaystyle F{F}^{†}=F^{†}F=I}$ holds, where${\displaystyle F^{†}}$ is theHermitian adjoint of${\displaystyle F}$. Alternately, one can check that orthogonal vectors ofnorm 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${\displaystyle F^{-1}=F^{†}}$. 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.

Thequantum gates used in the circuit of${\displaystyle n}$ qubits are theHadamard gate and thedyadic rationalphase gate${\displaystyle R_k}$:

The circuit is composed of${\displaystyle H}$ gates and thecontrolled version of${\displaystyle R_k}$:

An orthonormal basis${\displaystyle S}$ is composed of basis states

${\displaystyle S=\{|0⟩,\dots ,|2^n-1⟩\}}$

These basis states span all possible states of the qubits. As in, each${\displaystyle |x⟩\in S}$ is:

${\displaystyle |x⟩=|x_1{x}_2\dots x_n⟩=|x_1⟩\otimes |x_2⟩\otimes \cdots \otimes |x_n⟩}$

where, withtensor product notation${\displaystyle \otimes }$,${\displaystyle |x_j⟩}$ indicates that qubit${\displaystyle j}$ is in state${\displaystyle x_j}$, with${\displaystyle x_j}$ either 0 or 1. By convention, the basis state index${\displaystyle x}$ is thebinary number encoded by the${\displaystyle x_j}$, with${\displaystyle x_1}$ the most significant bit.

The action of the Hadamard gate is${\displaystyle H|x_j⟩=\left(\frac{1}{\sqrt{2}}\right)\left(|0⟩+e^{2\pi i{x}_j{2}^{-1}}|1⟩\right)}$, where the sign depends on${\displaystyle x_j}$.

The quantum Fourier transform can be written as the tensor product of a series of terms:

${\displaystyle \text{QFT}(|x⟩)=\frac{1}{\sqrt{N}}\underset{j=1}{\overset{n}{⨂}}\left(|0⟩+{\omega }_N^{x{2}^{n-j}}|1⟩\right).}$

Using the fractional binary notation

${\displaystyle [0.x_1\dots x_m]=\sum _{k=1}^m{x}_k{2}^{-k},}$

the action of the quantum Fourier transform can be expressed in a compact manner:

${\displaystyle \text{QFT}(|x_1{x}_2\dots x_n⟩)=\frac{1}{\sqrt{N}}\left(|0⟩+e^{2\pi i[0.x_n]}|1⟩\right)\otimes \left(|0⟩+e^{2\pi i[0.x_{n-1}{x}_n]}|1⟩\right)\otimes \cdots \otimes \left(|0⟩+e^{2\pi i[0.x_1{x}_2\dots x_n]}|1⟩\right).}$

To obtain this state from the circuit depicted above, aswap operation of the qubits must be performed to reverse their order. At most${\displaystyle n/2}$ swaps are required.^[5]

Because the discrete Fourier transform, an operation onn qubits, can be factored into the tensor product ofn single-qubit operations, it is easily represented as aquantum circuit (up to an order reversal of the output). Each of those single-qubit operations can be implemented efficiently using oneHadamard gate and a linear number ofcontrolledphase gates. The first term requires one Hadamard gate and${\displaystyle (n-1)}$ controlled phase gates, the next term requires one Hadamard gate and${\displaystyle (n-2)}$ controlled phase gate, and each following term requires one fewer controlled phase gate. Summing up the number of gates, excluding the ones needed for the output reversal, gives${\displaystyle n+(n-1)+\cdots +1=n(n+1)/2=O(n^2)}$ gates, which is quadratic polynomial in the number of qubits. This value is much smaller than for the classical Fourier transformation.^[7]

The circuit-level implementation of the quantum Fourier transform on a linear nearest neighbor architecture has been studied before.^[8][9] Thecircuit depth is linear in the number of qubits.

The quantum Fourier transform on three qubits,${\displaystyle F_8}$ with${\displaystyle n=3,N=8=2^3}$, is represented by the following transformation:

${\displaystyle \text{QFT}:|x⟩\mapsto \frac{1}{\sqrt{8}}\sum _{k=0}^7{\omega }^{xk}|k⟩,}$

where${\displaystyle \omega ={\omega }_8}$ is an eighthroot of unity satisfying${\displaystyle {\omega }^8={\left(e^{\frac{i2\pi }{8}}\right)}^8=1}$.

The matrix representation of the Fourier transform on three qubits is:

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

${\displaystyle \text{QFT}(|x_1,x_2,x_3⟩)=\frac{1}{\sqrt{8}}\left(|0⟩+e^{2\pi i[0.x_3]}|1⟩\right)\otimes \left(|0⟩+e^{2\pi i[0.x_2{x}_3]}|1⟩\right)\otimes \left(|0⟩+e^{2\pi i[0.x_1{x}_2{x}_3]}|1⟩\right).}$

The following sketch shows the respective circuit for${\displaystyle n=3}$ (with reversed order of output qubits with respect to the proper QFT):

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

Using the generalizedFourier transform on finite (abelian) groups, there are actually two natural ways to define a quantum Fourier transform on ann-qubitquantum register. The QFT as defined above is equivalent to the DFT, which considers these n qubits as indexed by the cyclic group${\displaystyle \mathbb{Z}/2^n\mathbb{Z}}$. However, it also makes sense to consider the qubits as indexed by theBoolean group${\displaystyle (\mathbb{Z}/2\mathbb{Z}{)}^n}$, and in this case the Fourier transform is theHadamard transform. This is achieved by applying aHadamard gate to each of the n qubits in parallel.^[10][11]Shor's algorithm uses both types of Fourier transforms, an initial Hadamard transform as well as a QFT.

The Fourier transform can be formulated forgroups other than the cyclic group, and extended to the quantum setting.^[12] For example, consider the symmetric group${\displaystyle S_n}$.^[13][14] The Fourier transform can be expressed in matrix form

${\displaystyle {\mathfrak{F}}_n=\sum _{\lambda \in {\mathrm{\Lambda }}_n}\sum _{p,q\in \mathcal{P}(\lambda )}\sum _{g\in S_n}\sqrt{\frac{d_{\lambda }}{n!}}[\lambda (g){]}_{q,p}|\lambda ,p,q⟩⟨g|,}$

where${\displaystyle [\lambda (g){]}_{q,p}}$ is the${\displaystyle (q,p)}$ element of the matrix representation of${\displaystyle \lambda (g)}$,${\displaystyle \mathcal{P}(\lambda )}$ is the set of paths from the root node to${\displaystyle \lambda }$ in theBratteli diagram of${\displaystyle S_n}$,${\displaystyle {\mathrm{\Lambda }}_n}$ is the set of representations of${\displaystyle S_n}$ indexed byYoung diagrams, and${\displaystyle g}$ is a permutation.

The discrete Fourier transform can also beformulated over a finite field${\displaystyle F_q}$, and a quantum version can be defined.^[15] Consider${\displaystyle N=q=p^n}$. Let${\displaystyle \varphi :GF(q)\to GF(p)}$ be an arbitrary linear map (trace, for example). Then for each${\displaystyle x\in GF(q)}$ define

${\displaystyle F_{q,\varphi }:|x⟩\mapsto \frac{1}{\sqrt{q}}\sum _{y\in GF(q)}{\omega }^{\varphi (xy)}|y⟩}$

for${\displaystyle \omega =e^{2\pi i/p}}$ and extend${\displaystyle F_{q,\varphi }}$ linearly.

• Parthasarathy, K. R. (2006).Lectures on Quantum Computation, Quantum Error Correcting Codes and Information Theory. Tata Institute of Fundamental Research.ISBN 978-81-7319-688-1.
• Preskill, John (September 1998)."Lecture Notes for Physics 229: Quantum Information and Computation"(PDF).

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

• Transforms
• Quantum algorithms
• Fourier analysis

• Webarchive template wayback links
• All articles with incomplete citations
• Articles with incomplete citations from June 2024
• Articles with short description
• Short description matches Wikidata
• Use American English from January 2019
• All Wikipedia articles written in American English