Quantum Fourier transform: Difference between revisions

Revision as of 15:22, 21 August 2015

Latest revision as of 01:54, 27 July 2025

(215 intermediate revisions by 92 users not shown)

Line 1:

{{Short description|Change of basis applied in quantum computing}}

In [[quantum computing]], the '''quantum Fourier transform''' is a [[linear transformation]] on [[qubit|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 [[eigenvalue]]s of a [[unitary operator]], and algorithms for the [[hidden subgroup problem]].

{{Use American English|date=January 2019}}In [[quantum computing]], the '''quantum Fourier transform (QFT)''' is a [[linear transformation]] on [[qubit|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 [[eigenvalue]]s of a [[unitary operator]], and algorithms for the [[hidden subgroup problem]]. The quantum Fourier transform was discovered by [[Don Coppersmith]].<ref name="dc_qft">{{cite report |type=Preprint |last1=Coppersmith |first1=D. |title=An approximate Fourier transform useful in quantum factoring |date=2002 |arxiv=quant-ph/0201067 }}</ref> With small modifications to the QFT, it can also be used for performing fast [[Integer (computer science)|integer]] arithmetic operations such as addition and multiplication.<ref>{{cite arXiv |last=Draper |first=Thomas G. |eprint=quant-ph/0008033 |title=Addition on a Quantum Computer |date=7 Aug 2000}}</ref><ref>{{cite journal |last1=Ruiz-Perez |first1=Lidia |last2=Juan Carlos |first2=Garcia-Escartin |title=Quantum arithmetic with the quantum Fourier transform |journal=Quantum Information Processing |arxiv=1411.5949v2 |date=2 May 2017 |volume=16 |issue=6 |page=152 |doi=10.1007/s11128-017-1603-1 |bibcode=2017QuIP...16..152R |s2cid=10948948}}</ref><ref>{{cite journal | last=Şahin | first=Engin | title=Quantum arithmetic operations based on quantum Fourier transform on signed integers | year=2020 | journal=International Journal of Quantum Information | volume=18 | issue=6 | pages=2050035 | issn=1793-6918 | doi=10.1142/s0219749920500355 | arxiv=2005.00443v3| bibcode=2020IJQI...1850035S }}</ref>

The quantum Fourier transform can be performed efficiently on a quantum computer, with a particular decomposition into athe product of simpler [[unitary matrix|unitary matrices]]. Using a simple decomposition, theThe discrete Fourier transform on <math>2^n</math> amplitudes can be implemented as a [[quantum circuit]] consisting of only <math>O(n^2)</math> [[Hadamard gate]]s and [[Quantum logic gate#Controlled gates|controlled]] [[phase shift gate]]s, where <math>n</math> is the number of qubits.<ref name=":0">{{cite book | authordoi= [[Michael Nielsen]] and Isaac Chuang10.1017/CBO9780511976667 | title=Quantum Computation and Quantum Information |date=2012 publisher|last1=CambridgeNielsen University|first1=Michael PressA. | ___locationlast2=CambridgeChuang | yearfirst2=2000Isaac L. | isbn=0978-5211-63503107-9 | oclc=00217-3 174527496}}</ref> This can be compared with the classical discrete Fourier transform, which takes <math>O(n2^n)</math> gates (where <math>n</math> is the number of bits), which is exponentially more than <math>O(n^2)</math>. 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 quantum Fourier transform acts on a [[quantum state]] vector (a [[quantum register]]), and the classical [[discrete 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 of [[floating-point number]]s, and in the quantum case it is a sequence of [[probability amplitude]]s for all the possible outcomes upon [[Measurement in quantum mechanics|measurement]] (the outcomes are the ''basis states'', or ''[[eigenstate]]s''). Because measurement [[wave-function collapse|collapses]] 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 today require only <math>O(n \log n)</math> gates to achieve an efficient approximation.<ref>L. Hales, S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.&nbsp;515, November 12–14, 2000</ref>

The best quantum Fourier transform algorithms known (as of late 2000) require only <math>O(n \log n)</math> gates to achieve an efficient approximation, provided that a [[Quantum logic gate#Controlled gates|controlled]] [[Quantum gate#Phase shift gates|phase gate]] is implemented as a native operation.<ref>{{Cite book |last1=Hales |first1=L. |last2=Hallgren |first2=S. |title=Proceedings 41st Annual Symposium on Foundations of Computer Science |chapter=An improved quantum Fourier transform algorithm and applications |date=November 12–14, 2000 |pages=515–525 |doi=10.1109/SFCS.2000.892139 |isbn=0-7695-0850-2 |citeseerx=10.1.1.29.4161 |s2cid=424297}}</ref>

== Definition ==

The quantum Fourier transform is the classical discrete Fourier transform applied to the vector of amplitudes of a quantum state., Thewhich classicalhas (unitary) Fourier transform acts on a [[vector (mathematics and physics)|vector]] inlength <math>\mathbb{C}N = 2^Nn</math>, (''x''₀,if ...,it ''x''_''N''−1)is andapplied mapsto ita toregister theof vector (''y''<submath>0n</submath>, qubits..., ''y''_''N''−1) according to the formula:

The '''classical Fourier transform''' acts on a [[vector (mathematics and physics)|vector]] <math>(x_0, x_1, \ldots , x_{N-1}) \in \mathbb{C}^N</math> and maps it to the vector

<math>(y_0, y_1, \ldots , y_{N-1}) \in \mathbb{C}^N</math> according to the formula

: <math>y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omegaomega_N^{-jk}, \quad k = 0, 1, 2, \ldots, N - 1,</math>

where <math>\omega^{jk}omega_N = e^{\frac{2 \pi i\frac{j\, k}{N}}</math> is aan ''N''^-th [[root of unity]].

Similarly, the '''quantum Fourier transform''' acts on a quantum state <math display="inline">|x\rangle = \sum_{ij=0}^{N-1} x_ix_j |ij\rangle</math> and maps it to a quantum state <math display="inline">\sum_{ij=0}^{N-1} y_iy_j |ij\rangle</math> according to the formula:

: <math>y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omegaomega_N^{jk}, \quad k = 0, 1, 2, \ldots, N - 1.</math>

(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.)

with <math>\omega^{jk}</math> defined as above.

Since <math>\omega_N^l</math> is a rotation, the '''inverse quantum Fourier transform''' acts similarly but with

This can also be expressed as the map

: <math>|j\rangle \mapstox_j = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} y_k \omegaomega_N^{-jk}, |k\rangle.quad j = 0, 1, 2, \ldots, N - 1,</math>

In case that <math>|x\rangle </math> is a basis state, the quantum Fourier transform can also be expressed as the map

Equivalently, the quantum Fourier transform can be viewed as a unitary matrix ([[quantum gate]], similar to a logic gate for classical computers) acting on quantum state vectors, where the unitary matrix <math>F_N</math> is given by

:<math>

: <math>\operatorname{QFT}: |x\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} \omega_N^{xk} |k\rangle.</math>

Equivalently, the quantum Fourier transform can be viewed as a [[unitary matrix]] (or [[quantum gate]]) acting on quantum state vectors, where the unitary matrix <math>F_N</math> is the [[DFT matrix]]

: <math>

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

</math>

where <math>\omega = \omega_N</math>. For example, in the case of <math>N = 4 = 2^2</math> and phase <math>\omega = i</math> the transformation matrix is

: <math>

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}

</math>

{{see also|Generalizations of Pauli matrices#Construction: The clock and shift matrices}}

Here <math>\omega = e^{\frac{2 \pi i}{N}}</math> is a primitive ''N''^th [[root of unity]].

== Properties ==

=== Unitarity ===

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 <math>FF^{\dagger}=F^{\dagger}F=I</math> holds, where <math>F^\dagger</math> is the [[Hermitian adjoint]] of <math>F</math>. Alternately, one can check that vectors of [[norm (mathematics)|norm]] 1 get mapped to vectors of norm 1.

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 <math>FF^{\dagger}=F^{\dagger}F=I</math> holds, where <math>F^\dagger</math> is the [[Hermitian adjoint]] of <math>F</math>. Alternately, one can check that orthogonal vectors of [[norm (mathematics)|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 <math>F^{-1}=F^{\dagger}</math>. 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.

== Circuit implementation ==

The [[quantum gate]]s used in the circuit of <math>n</math> qubits are the [[Quantum gate#Hadamard gate|Hadamard gate]] and the [[dyadic rational]] [[Quantum gate#Phase shift gates|phase gate]] <math>R_k</math>:

[[Image:Quantum Fourier transform on n qubits.svg|600px|thumb|[[Quantum circuit]] representation of the quantum Fourier transform]]

<math>H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \qquad

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. Suppose ''N'' = 2^''n''. We have the orthonormal basis consisting of the vectors

\text{and} \qquad

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

The circuit is composed of <math>H</math> gates and the [[Quantum logic gate#Controlled gates|controlled]] version of <math>R_k</math>:

[[File:Q fourier nqubits.png|700px|Quantum circuit for Quantum-Fourier-Transform with n qubits (without rearranging the order of output states) using the fractional binary notation defined below.]]

An orthonormal basis consists of the basis states

:<math> |0\rangle, \ldots , |2^n - 1\rangle. </math>

TheThese basis states enumeratespan all the possible states of the qubits:

:<math> | x \rangle = | x_1 x_2 \ldots x_n \rangle = | x_1 \rangle \otimes | x_2 \rangle \otimes \cdots \otimes | x_n \rangle</math>

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

:<math> x = x_1 2^{n-1} + x_2 2^{n-2} +\cdots + x_n 2^0.\quad </math>

where, with [[tensor product]] notation <math>\otimes</math>, <math>|x_j\rangle</math> indicates that qubit <math>j</math> is in state <math>x_j</math>, with <math>x_j</math> either 0 or 1. By convention, the basis state index <math>x</math> is the [[binary number]] encoded by the <math>x_j</math>, with <math>x_1</math> the most significant bit.

It is also useful to borrow fractional binary notation:

:<math> [0. x_1 \ldots x_m] = \sum_{k = 1}^m x_k 2^{-k}.</math>

For instance, <math>[0.x_1] = \frac{x_1}{2}</math> and <math>[0.x_1 x_2] = \frac{x_1}{2}+\frac{x_2}{2^2}.</math>

The action of the Hadamard gate is <math>H|x_j\rangle=\left(\frac{1}{\sqrt{2}}\right)\left(|0\rangle+e^{2\pi i x_j 2^{-1}}|1\rangle \right) </math>, where the sign depends on <math>x_i</math>.

With this notation, the action of the quantum Fourier transform can be expressed as:

:<math>|x_1 x_2 \ldots x_n \rangle \mapsto \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),</math>

where the output qubit 1 is in a superposition of state <math>|0\rangle</math> and <math>e^{2 \pi i \, [0.x_n] }|1\rangle</math>, and so on for the other qubits.

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

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]]. In fact, each of those single-qubit operations can be implemented efficiently using a [[Hadamard gate]] and [[Quantum_gate#Controlled_gates|controlled]] [[Quantum_gate#Phase_shift_gates|phase gate]]s. The first term requires one Hadamard gate, the next one requires a Hadamard gate and a controlled phase gate, and each following term requires an additional controlled phase gate. Summing up the number of gates gives <math>1 + 2 + \cdots + n = n(n+1)/2 = O(n^2)</math> gates, which is polynomial in the number of qubits.

: <math>

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

</math>

Using the fractional binary notation

:<math> [0. x_1 \ldots x_m] = \sum_{k = 1}^m x_k 2^{-k},</math>

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

:<math>\text{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).</math>

To obtain this state from the circuit depicted above, a [[Quantum logic gate#Swap_gate|swap operation]] of the qubits must be performed to reverse their order. At most <math>n/2</math> swaps are required.<ref name=":0" />

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 [[Quantum gate#Controlled gates|controlled]] [[Quantum gate#Phase shift gates|phase gate]]s. The first term requires one Hadamard gate and <math>(n-1)</math> controlled phase gates, the next term requires one Hadamard gate and <math>(n-2)</math> 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 <math>n + (n-1) + \cdots + 1 = n(n+1)/2 = O(n^2)</math> gates, which is quadratic polynomial in the number of qubits. This value is much smaller than for the classical Fourier transformation.<ref>{{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}}</ref>

The circuit-level implementation of the quantum Fourier transform on a linear nearest neighbor architecture has been studied before.<ref>{{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 }}</ref><ref>{{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 }}</ref> The [[Circuit complexity|circuit depth]] is linear in the number of qubits.

== Example ==

Consider theThe quantum Fourier transform on 3three qubits., It<math>F_8</math> with <math>n=3, N=8=2^3</math>, is represented by the following transformation:

:<math>\text{QFT}: |x\rangle \mapsto \frac{1}{\sqrt{8}} \sum_{k=0}^{7} \omega^{xk} |k\rangle, </math>

where <math>\omega = \omega_{8}</math> is an eighth [[root of unity]] satisfying <math>\omega^8=\left(e^{\frac{i2\pi}{8}}\right)^8=1</math>.

:<math>|j\rangle \mapsto \frac{1}{\sqrt{2^3}} \sum_{k=0}^{2^3-1} \omega^{jk} |k\rangle, </math>

where <math>\omega</math> is a primitive eighth [[root of unity]] satisfying <math>\omega^8=\left(e^{\frac{2\pi i}{8}}\right)^8=1</math> (since <math>N = 2^3 = 8</math>).

The matrix representingrepresentation thisof transformationthe Fourier transform on 3three qubits is:

:<math>

F_{2^3}F_8 = \frac{1}{\sqrt{2^38}} \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 \\

Line 92 ⟶ 126:

</math>

The 3-qubit quantum Fourier transform iscan thebe followingrewritten operationas:

:<math>\text{QFT}(|x_1, x_2, x_3 \rangle \mapsto) = \frac{1}{\sqrt{2^38}} \ \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).</math>

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

This quantum circuit implements the quantum Fourier transform on the quantum state <math>|x_1,x_2,x_3\rangle</math>.

[[File:Q fourier 3qubits.png|600px|QFT for 3 Qubits (without rearranging the order of the output qubits)]]

[[File:Quantum Fourier transform on three qubits.svg|550px]]

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

The [[quantum gate]]s used in the circuit above are the [[Quantum_gate#Hadamard_gate|Hadamard gate]] and the [[Quantum_gate#Controlled_gates|controlled]] [[Quantum_gate#Phase_shift_gates|phase gate]] <math>R_\theta</math>.

== Relation to quantum Hadamard transform ==

As calculated above, the number of gates used is <math>n(n+1)/2</math> which is equal to 6, for&nbsp;''n''&nbsp;=&nbsp;3.

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

Using the generalized [[Fourier transform on finite groups|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 <math>\Z / 2^n \Z</math>. However, it also makes sense to consider the qubits as indexed by the [[Boolean group]] <math>(\Z / 2 \Z)^n</math>, 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.<ref>[https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12-13] {{Webarchive|url=https://web.archive.org/web/20210501173437/https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf |date=2021-05-01 }}{{full|date=June 2024}}</ref><ref>[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]</ref> [[Shor's algorithm]] uses both types of Fourier transforms, an initial Hadamard transform as well as a QFT.

== For other groups ==

The Fourier transform can be formulated for [[Fourier transform on finite groups|groups other than the cyclic group]], and extended to the quantum setting.<ref>{{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 }}</ref> For example, consider the symmetric group <math>S_n</math>.<ref>{{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 }}</ref><ref>{{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 }}</ref> The Fourier transform can be expressed in matrix form

: <math>\mathfrak{F}_n = \sum_{\lambda \in \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\rangle \langle g|,</math>

where <math>[\lambda(g)]_{q,p}</math> is the <math>(q, p)</math> element of the matrix representation of <math>\lambda(g)</math>, <math>\mathcal{P}(\lambda)</math> is the set of paths from the root node to <math>\lambda</math> in the [[Bratteli diagram]] of <math>S_n</math>, <math>\Lambda_n</math> is the set of representations of <math>S_n</math> indexed by [[Young diagram]]s, and <math>g</math> is a permutation.

== Over a finite field ==

The discrete Fourier transform can also be [[Discrete_Fourier_transform_over_a_ring#Finite_fields|formulated over a finite field]] <math>F_q</math>, and a quantum version can be defined.<ref>{{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 }}</ref> Consider <math>N = q = p^n</math>. Let <math>\phi: GF(q) \to GF(p)</math> be an arbitrary linear map (trace, for example). Then for each <math>x \in GF(q)</math> define

: <math>F_{q,\phi}: |x\rangle \mapsto \frac{1}{\sqrt{q}} \sum_{y \in GF(q)} \omega^{\phi(xy)}|y \rangle</math>

for <math>\omega = e^{2\pi i/p}</math> and extend <math>F_{q,\phi}</math> linearly.

== References ==

{{reflist}}

<references/>

* [[K. R. Parthasarathy (probabilist)|K. R. Parthasarathy]], ''Lectures on Quantum Computation and Quantum Error Correcting Codes'' (Indian Statistical Institute, Delhi Center, June 2001)

==Further reading==

* [[John Preskill]], ''Lecture Notes for Physics 229: Quantum Information and Computation'' (CIT, September 1998)

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

==External links==

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

Line 116 ⟶ 172:

[[Category:Transforms]]

[[Category:Quantum algorithms]]

[[Category:Fourier analysis]]