quantum Fourier transform

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

The classical Fourier transform acts on a vector $(x\_0,\; x\_1,\; \backslash ldots\; ,\; x\_\{N-1\})\; \backslash in\; \backslash mathbb\{C\}^N$ and maps it to the vector

$(y\_0,\; y\_1,\; \backslash ldots\; ,\; y\_\{N-1\})\; \backslash in\; \backslash mathbb\{C\}^N$ according to the formula

: $y\_k\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\}\}\; \backslash sum\_\{j=0\}^\{N-1\}\; x\_j\; \backslash omega\_N^\{-jk\},\; \backslash quad\; k\; =\; 0,\; 1,\; 2,\; \backslash ldots,\; N\; -\; 1,$

where $\backslash omega\_N\; =\; e^\{\backslash frac\{2\; \backslash pi\; i\}\{N\}\}$ is an N-th root of unity.

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

: $y\_k\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\}\}\; \backslash sum\_\{j=0\}^\{N-1\}\; x\_j\; \backslash omega\_N^\{jk\},\; \backslash quad\; k\; =\; 0,\; 1,\; 2,\; \backslash ldots,\; 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 $\backslash omega\_N^l$ is a rotation, the inverse quantum Fourier transform acts similarly but with

: $x\_j\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\}\}\; \backslash sum\_\{k=0\}^\{N-1\}\; y\_k\; \backslash omega\_N^\{-jk\},\; \backslash quad\; j\; =\; 0,\; 1,\; 2,\; \backslash ldots,\; N\; -\; 1,$

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

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

Equivalently, the quantum Fourier transform can be viewed as a unitary matrix (or quantum gate) acting on quantum state vectors, where the unitary matrix $F\_N$ is the DFT matrix

: $$

F_N = \frac{1}{\sqrt{N}} \begin{bmatrix}

1 & 1 & 1 & 1 & \cdots & 1 \\

1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{N-1} \\

1 & \omega^2 & \omega^4 & \omega^6 & \cdots & \omega^{2(N-1)} \\

1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{3(N-1)} \\

\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\

1 & \omega^{N-1} & \omega^{2(N-1)} & \omega^{3(N-1)} & \cdots & \omega^{(N-1)(N-1)}

\end{bmatrix},

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

: $$

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}}

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^\{\backslash dagger\}=F^\{\backslash dagger\}F=I$ holds, where $F^\backslash 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^\{\backslash 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.

The quantum gates used in the circuit of $n$ qubits are the Hadamard gate and the dyadic rational phase gate $R\_k$:

\text{and} \qquad

R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{i2\pi/2^k} \end{pmatrix}

The circuit is composed of $H$ gates and the controlled version of $R\_k$:

File:Q fourier nqubits.png

An orthonormal basis consists of the basis states

:$|0\backslash rangle,\; \backslash ldots\; ,\; |2^n\; -\; 1\backslash rangle.$

These basis states span all possible states of the qubits:

:$|\; x\; \backslash rangle\; =\; |\; x\_1\; x\_2\; \backslash ldots\; x\_n\; \backslash rangle\; =\; |\; x\_1\; \backslash rangle\; \backslash otimes\; |\; x\_2\; \backslash rangle\; \backslash otimes\; \backslash cdots\; \backslash otimes\; |\; x\_n\; \backslash rangle$

where, with tensor product notation $\backslash otimes$, $|x\_j\backslash rangle$ indicates that qubit $j$ is in state $x\_j$, with $x\_j$ either 0 or 1. By convention, the basis state index $x$ is the binary number encoded by the $x\_j$, with $x\_1$ the most significant bit.

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

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

: $$

\text{QFT}(|x\rangle) = \frac{1}{\sqrt{N}} \bigotimes_{j=1}^{n} \left( |0\rangle + \omega_N^{x2^{n-j}} |1\rangle \right).

Using the fractional binary notation

:$[0.\; x\_1\; \backslash ldots\; x\_m]\; =\; \backslash sum\_\{k\; =\; 1\}^m\; x\_k\; 2^\{-k\},$

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

:$\backslash text\{QFT\}(|x\_1\; x\_2\; \backslash ldots\; x\_n\; \backslash rangle)\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\}\}\; \backslash \; \backslash left(|0\backslash rangle\; +\; e^\{2\; \backslash pi\; i\; \backslash ,\; [0.x\_n]\; \}|1\backslash rangle\backslash right)\; \backslash otimes\; \backslash left(|0\backslash rangle\; +\; e^\{2\; \backslash pi\; i\; \backslash ,\; [0.x\_\{n-1\}\; x\_n]\; \}|1\backslash rangle\backslash right)\; \backslash otimes\; \backslash cdots\; \backslash otimes\; \backslash left(|0\backslash rangle\; +\; e^\{2\; \backslash pi\; i\; \backslash ,\; [0.x\_1\; x\_2\; \backslash ldots\; x\_n]\; \}|1\backslash rangle\backslash right).$

To obtain this state from the circuit depicted above, a swap operation of the qubits must be performed to reverse their order. At most $n/2$ swaps are required.

Because the discrete Fourier transform, an operation on n qubits, can be factored into the tensor product of n single-qubit operations, it is easily represented as a quantum circuit (up to an order reversal of the output). Each of those single-qubit operations can be implemented efficiently using one Hadamard gate and a linear number of controlled phase gates. The first term requires one Hadamard gate and $(n-1)$ controlled phase gates, the next term requires one Hadamard gate and $(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 $n\; +\; (n-1)\; +\; \backslash 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.{{Cite book |last1=Kurgalin |first1=Sergei |title=Concise guide to quantum computing: algorithms, exercises, and implementations |last2=Borzunov |first2=Sergei |date=2021 |publisher=Springer |isbn=978-3-030-65054-4 |series=Texts in computer science |location=Cham}}

The circuit-level implementation of the quantum Fourier transform on a linear nearest neighbor architecture has been studied before.{{cite journal |last1=Fowler |first1=A.G. |last2=Devitt |first2=S.J. |last3=Hollenberg |first3=L.C.L. |title=Implementation of Shor's algorithm on a linear nearest neighbour qubit array |journal=Quantum Information and Computation |date=July 2004 |volume=4 |issue=4 |pages=237–251 |doi=10.26421/QIC4.4-1 }}{{cite journal |last1=Maslov |first1=Dmitri |title=Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures |journal=Physical Review A |date=15 November 2007 |volume=76 |issue=5 |page=052310 |doi=10.1103/PhysRevA.76.052310 |s2cid=18645435 |arxiv=quant-ph/0703211 |bibcode=2007PhRvA..76e2310M }} The circuit depth is linear in the number of qubits.

The quantum Fourier transform on three qubits, $F\_8$ with $n=3,\; N=8=2^3$, is represented by the following transformation:

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

where $\backslash omega\; =\; \backslash omega\_\{8\}$ is an eighth root of unity satisfying $\backslash omega^8=\backslash left(e^\{\backslash frac\{i2\backslash pi\}\{8\}\}\backslash right)^8=1$.

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

:$$

F_8 = \frac{1}{\sqrt{8}} \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}.

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

:$\backslash text\{QFT\}(|x\_1,\; x\_2,\; x\_3\; \backslash rangle\; )\; =\; \backslash frac\{1\}\{\backslash sqrt\{8\}\}\; \backslash \; \backslash left(|0\backslash rangle\; +\; e^\{2\; \backslash pi\; i\; \backslash ,\; [0.x\_3]\; \}|1\backslash rangle\backslash right)\; \backslash otimes\; \backslash left(|0\backslash rangle\; +\; e^\{2\; \backslash pi\; i\; \backslash ,\; [0.x\_2\; x\_3]\; \}|1\backslash rangle\backslash right)\; \backslash otimes\; \backslash left(|0\backslash rangle\; +\; e^\{2\; \backslash pi\; i\; \backslash ,\; [0.x\_1\; x\_2\; x\_3]\; \}|1\backslash rangle\backslash right).$

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

File:Q fourier 3qubits.png

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

{{see also|Hadamard transform#Quantum computing applications}}

Using the generalized Fourier transform on finite (abelian) groups, there are actually two natural ways to define a quantum Fourier transform on an n-qubit quantum register. The QFT as defined above is equivalent to the DFT, which considers these n qubits as indexed by the cyclic group $\backslash Z\; /\; 2^n\; \backslash Z$. However, it also makes sense to consider the qubits as indexed by the Boolean group $(\backslash Z\; /\; 2\; \backslash Z)^n$, and in this case the Fourier transform is the Hadamard transform. This is achieved by applying a Hadamard gate to each of the n qubits in parallel.[https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12-13]{{full|date=June 2024}}[https://web.archive.org/web/20210713134541/https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-5] Shor's algorithm uses both types of Fourier transforms, an initial Hadamard transform as well as a QFT.

The Fourier transform can be formulated for groups other than the cyclic group, and extended to the quantum setting.{{cite report |type=Preprint |last1=Moore |first1=Cristopher |last2=Rockmore |first2=Daniel |last3=Russell |first3=Alexander |title=Generic Quantum Fourier Transforms |date=2003 |arxiv=quant-ph/0304064 }} For example, consider the symmetric group $S\_n$.{{cite journal |last1=Kawano |first1=Yasuhito |last2=Sekigawa |first2=Hiroshi |title=Quantum Fourier transform over symmetric groups — improved result |journal=Journal of Symbolic Computation |date=July 2016 |volume=75 |pages=219–243 |doi=10.1016/j.jsc.2015.11.016 }}{{cite book |doi=10.1145/258533.258548 |chapter=Quantum computation of Fourier transforms over symmetric groups |title=Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 |date=1997 |last1=Beals |first1=Robert |pages=48–53 |isbn=0-89791-888-6 }} The Fourier transform can be expressed in matrix form

: $\backslash mathfrak\{F\}\_n\; =\; \backslash sum\_\{\backslash lambda\; \backslash in\; \backslash Lambda\_n\}\; \backslash sum\_\{p,q\; \backslash in\; \backslash mathcal\{P\}(\backslash lambda)\}\; \backslash sum\_\{g\; \backslash in\; S\_n\}\; \backslash sqrt\{\backslash frac\{d\_\backslash lambda\}\{n!\}\}[\backslash lambda(g)]\_\{q,p\}\; |\backslash lambda,\; p,\; q\backslash rangle\; \backslash langle\; g|,$

where $[\backslash lambda(g)]\_\{q,p\}$ is the $(q,\; p)$ element of the matrix representation of $\backslash lambda(g)$, $\backslash mathcal\{P\}(\backslash lambda)$ is the set of paths from the root node to $\backslash lambda$ in the Bratteli diagram of $S\_n$, $\backslash Lambda\_n$ is the set of representations of $S\_n$ indexed by Young diagrams, and $g$ is a permutation.

The discrete Fourier transform can also be formulated over a finite field $F\_q$, and a quantum version can be defined.{{cite journal |last1=de Beaudrap |first1=Niel |last2=Cleve |first2=Richard |last3=Waltrous |first3=John |title=Sharp Quantum versus Classical Query Complexity Separations |journal=Algorithmica |date=8 November 2002 |volume=34 |issue=4 |pages=449–461 |doi=10.1007/s00453-002-0978-1 }} Consider $N\; =\; q\; =\; p^n$. Let $\backslash phi:\; GF(q)\; \backslash to\; GF(p)$ be an arbitrary linear map (trace, for example). Then for each $x\; \backslash in\; GF(q)$ define

: $F\_\{q,\backslash phi\}:\; |x\backslash rangle\; \backslash mapsto\; \backslash frac\{1\}\{\backslash sqrt\{q\}\}\; \backslash sum\_\{y\; \backslash in\; GF(q)\}\; \backslash omega^\{\backslash phi(xy)\}|y\; \backslash rangle$

for $\backslash omega\; =\; e^\{2\backslash pi\; i/p\}$ and extend $F\_\{q,\backslash phi\}$ linearly.

{{reflist}}

• {{cite book |last1=Parthasarathy |first1=K. R. |authorlink1=K. R. Parthasarathy (probabilist) |title=Lectures on Quantum Computation, Quantum Error Correcting Codes and Information Theory |date=2006 |publisher=Tata Institute of Fundamental Research |isbn=978-81-7319-688-1 }}
• {{cite web |last1=Preskill |first1=John |authorlink1=John Preskill |title=Lecture Notes for Physics 229: Quantum Information and Computation |date=September 1998 |url=https://web.gps.caltech.edu/~rls/book.pdf }}

• [http://demonstrations.wolfram.com/QuantumCircuitImplementingGroversSearchAlgorithm/ Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm]
• [http://demonstrations.wolfram.com/QuantumFourierTransformCircuit/ Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform]
• [http://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22Counting8%22%5D%2C%5B%22Chance8%22%5D%2C%5B%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%2C%22%E2%80%A6%22%5D%2C%5B%22Swap%22%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C%22Swap%22%2C1%2C1%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C%22Swap%22%2C1%2C1%2C%22Swap%22%5D%2C%5B1%2C1%2C1%2C%22Swap%22%2C%22Swap%22%5D%2C%5B%22H%22%5D%2C%5B%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C%22H%22%5D%2C%5B%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%86%E2%82%84%22%2C%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%5D%2C%5B%22Z%5E%E2%85%9F%E2%82%81%E2%82%82%E2%82%88%22%2C%22Z%5E%E2%85%9F%E2%82%86%E2%82%84%22%2C%22Z%5E%E2%85%9F%E2%82%83%E2%82%82%22%2C%22Z%5E%E2%85%9F%E2%82%81%E2%82%86%22%2C%22Z%5E%E2%85%9B%22%2C%22Z%5E%C2%BC%22%2C%22Z%5E%C2%BD%22%2C%22%E2%80%A2%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22H%22%5D%5D%7D Quirk online life quantum fourier transform]

{{quantum computing}}

{{DEFAULTSORT:Quantum Fourier Transform}}

Category:Transforms

Category:Quantum algorithms

Category:Fourier analysis