Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Quantum Fourier transform
open-in-new
<h2 id="definition">Definition</h2> <p>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 {\displaystyle N=2^{n}} if it is applied to a register of n {\displaystyle n} qubits. </p><p>The classical Fourier transform acts on a <a href="/facts/Vector_(mathematics_and_physics)/U8mM7A5F">vector</a> ( x 0 , x 1 , … , x N − 1 ) ∈ C N {\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}} and maps it to the vector ( y 0 , y 1 , … , y N − 1 ) ∈ C N {\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}} according to the formula </p> y k = 1 N ∑ j = 0 N − 1 x j ω N − j k , k = 0 , 1 , 2 , … , N − 1 , {\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{N}^{-jk},\quad k=0,1,2,\ldots ,N-1,} <p>where ω N = e 2 π i N {\displaystyle \omega _{N}=e^{\frac {2\pi i}{N}}} is an <i>N</i>-th <a href="/facts/Root_of_unity/EqH0ho1Y">root of unity</a>. </p><p>Similarly, the quantum Fourier transform acts on a quantum state | x ⟩ = ∑ j = 0 N − 1 x j | j ⟩ {\textstyle |x\rangle =\sum _{j=0}^{N-1}x_{j}|j\rangle } and maps it to a quantum state ∑ j = 0 N − 1 y j | j ⟩ {\textstyle \sum _{j=0}^{N-1}y_{j}|j\rangle } according to the formula </p> y k = 1 N ∑ j = 0 N − 1 x j ω N j k , k = 0 , 1 , 2 , … , N − 1. {\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}x_{j}\omega _{N}^{jk},\quad k=0,1,2,\ldots ,N-1.} <p>(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.) </p><p>Since ω N l {\displaystyle \omega _{N}^{l}} is a rotation, the inverse quantum Fourier transform acts similarly but with </p> x j = 1 N ∑ k = 0 N − 1 y k ω N − j k , j = 0 , 1 , 2 , … , N − 1 , {\displaystyle x_{j}={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}y_{k}\omega _{N}^{-jk},\quad j=0,1,2,\ldots ,N-1,} <p>In case that | x ⟩ {\displaystyle |x\rangle } is a basis state, the quantum Fourier transform can also be expressed as the map </p> QFT : | x ⟩ ↦ 1 N ∑ k = 0 N − 1 ω N x k | k ⟩ . {\displaystyle \operatorname {QFT} :|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle .} <p>Equivalently, the quantum Fourier transform can be viewed as a <a href="/facts/Unitary_matrix/8fsxv3KD">unitary matrix</a> (or <a href="/facts/Quantum_gate/EFV5sPCU">quantum gate</a>) acting on quantum state vectors, where the unitary matrix F N {\displaystyle F_{N}} is the <a href="/facts/DFT_matrix/oQM4frPU">DFT matrix</a> </p> F N = 1 N [ 1 1 1 1 ⋯ 1 1 ω ω 2 ω 3 ⋯ ω N − 1 1 ω 2 ω 4 ω 6 ⋯ ω 2 ( N − 1 ) 1 ω 3 ω 6 ω 9 ⋯ ω 3 ( N − 1 ) ⋮ ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω N − 1 ω 2 ( N − 1 ) ω 3 ( N − 1 ) ⋯ ω ( N − 1 ) ( N − 1 ) ] , {\displaystyle 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}},} <p>where ω = ω N {\displaystyle \omega =\omega _{N}} . For example, in the case of N = 4 = 2 2 {\displaystyle N=4=2^{2}} and phase ω = i {\displaystyle \omega =i} the transformation matrix is </p> F 4 = 1 2 [ 1 1 1 1 1 i − 1 − i 1 − 1 1 − 1 1 − i − 1 i ] {\displaystyle 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}}} <p class="note">See also: <a href="/facts/Generalizations_of_Pauli_matrices/SjqqBE28">Generalizations of Pauli matrices § Construction: The clock and shift matrices</a></p> <h2 id="properties">Properties</h2> <h3>Unitarity</h3> <p>Most of the properties of the quantum Fourier transform follow from the fact that it is a <a href="/facts/Unitary_transformation/DyvU0nms">unitary transformation</a>. This can be checked by performing <a href="/facts/Matrix_multiplication/lYDB6Ro2">matrix multiplication</a> and ensuring that the relation F F † = F † F = I {\displaystyle FF^{\dagger }=F^{\dagger }F=I} holds, where F † {\displaystyle F^{\dagger }} is the <a href="/facts/Hermitian_adjoint/gN6RHphd">Hermitian adjoint</a> of F {\displaystyle F} . Alternately, one can check that orthogonal vectors of <a href="/facts/Norm_(mathematics)/xIbR4uE1">norm</a> 1 get mapped to orthogonal vectors of norm 1. </p><p>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 † {\displaystyle 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. </p> <h2 id="circuit-implementation">Circuit implementation</h2> <p>The <a href="/facts/Quantum_gate/EFV5sPCU">quantum gates</a> used in the circuit of n {\displaystyle n} qubits are the <a href="/facts/Quantum_gate/EFV5sPCU">Hadamard gate</a> and the <a href="/facts/Dyadic_rational/LPwRYKaD">dyadic rational</a> <a href="/facts/Quantum_gate/EFV5sPCU">phase gate</a> R k {\displaystyle R_{k}} : </p><p> H = 1 2 ( 1 1 1 − 1 ) and R k = ( 1 0 0 e i 2 π / 2 k ) {\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{and}}\qquad R_{k}={\begin{pmatrix}1&0\\0&e^{i2\pi /2^{k}}\end{pmatrix}}} </p><p>The circuit is composed of H {\displaystyle H} gates and the <a href="/facts/Quantum_logic_gate/EFV5sPCU">controlled</a> version of R k {\displaystyle R_{k}} : </p><p>An orthonormal basis consists of the basis states </p> | 0 ⟩ , … , | 2 n − 1 ⟩ . {\displaystyle |0\rangle ,\ldots ,|2^{n}-1\rangle .} <p>These basis states span all possible states of the qubits: </p> | x ⟩ = | x 1 x 2 … x n ⟩ = | x 1 ⟩ ⊗ | x 2 ⟩ ⊗ ⋯ ⊗ | x n ⟩ {\displaystyle |x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_{n}\rangle } <p>where, with <a href="/facts/Tensor_product/7K3pR1ap">tensor product</a> notation ⊗ {\displaystyle \otimes } , | x j ⟩ {\displaystyle |x_{j}\rangle } indicates that qubit j {\displaystyle j} is in state x j {\displaystyle x_{j}} , with x j {\displaystyle x_{j}} either 0 or 1. By convention, the basis state index x {\displaystyle x} is the <a href="/facts/Binary_number/a6JDSRPs">binary number</a> encoded by the x j {\displaystyle x_{j}} , with x 1 {\displaystyle x_{1}} the most significant bit. </p><p>The action of the Hadamard gate is H | x j ⟩ = ( 1 2 ) ( | 0 ⟩ + e 2 π i x j 2 − 1 | 1 ⟩ ) {\displaystyle H|x_{j}\rangle =\left({\frac {1}{\sqrt {2}}}\right)\left(|0\rangle +e^{2\pi ix_{j}2^{-1}}|1\rangle \right)} , where the sign depends on x i {\displaystyle x_{i}} . </p><p>The quantum Fourier transform can be written as the tensor product of a series of terms: </p> QFT ( | x ⟩ ) = 1 N ⨂ j = 1 n ( | 0 ⟩ + ω N x 2 n − j | 1 ⟩ ) . {\displaystyle {\text{QFT}}(|x\rangle )={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +\omega _{N}^{x2^{n-j}}|1\rangle \right).} <p>Using the fractional binary notation </p> [ 0. x 1 … x m ] = ∑ k = 1 m x k 2 − k , {\displaystyle [0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k},} <p>the action of the quantum Fourier transform can be expressed in a compact manner: </p> QFT ( | x 1 x 2 … x n ⟩ ) = 1 N ( | 0 ⟩ + e 2 π i [ 0. x n ] | 1 ⟩ ) ⊗ ( | 0 ⟩ + e 2 π i [ 0. x n − 1 x n ] | 1 ⟩ ) ⊗ ⋯ ⊗ ( | 0 ⟩ + e 2 π i [ 0. x 1 x 2 … x n ] | 1 ⟩ ) . {\displaystyle {\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).} <p>To obtain this state from the circuit depicted above, a <a href="/facts/Quantum_logic_gate/EFV5sPCU">swap operation</a> of the qubits must be performed to reverse their order. At most n / 2 {\displaystyle n/2} swaps are required.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>Because the discrete Fourier transform, an operation on <i>n</i> qubits, can be factored into the tensor product of <i>n</i> single-qubit operations, it is easily represented as a <a href="/facts/Quantum_circuit/yuFDFFPa">quantum circuit</a> (up to an order reversal of the output). Each of those single-qubit operations can be implemented efficiently using one <a href="/facts/Hadamard_gate/JFD5uojA">Hadamard gate</a> and a linear number of <a href="/facts/Quantum_gate/EFV5sPCU">controlled</a> <a href="/facts/Quantum_gate/EFV5sPCU">phase gates</a>. The first term requires one Hadamard gate and ( n − 1 ) {\displaystyle (n-1)} controlled phase gates, the next term requires one Hadamard gate and ( n − 2 ) {\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 n + ( n − 1 ) + ⋯ + 1 = n ( n + 1 ) / 2 = O ( n 2 ) {\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.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> </p><p>The circuit-level implementation of the quantum Fourier transform on a linear nearest neighbor architecture has been studied before.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a><a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> The <a href="/facts/Circuit_complexity/6EzA9Tty">circuit depth</a> is linear in the number of qubits. </p> <h2 id="example">Example</h2> <p>The quantum Fourier transform on three qubits, F 8 {\displaystyle F_{8}} with n = 3 , N = 8 = 2 3 {\displaystyle n=3,N=8=2^{3}} , is represented by the following transformation: </p> QFT : | x ⟩ ↦ 1 8 ∑ k = 0 7 ω x k | k ⟩ , {\displaystyle {\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {8}}}\sum _{k=0}^{7}\omega ^{xk}|k\rangle ,} <p>where ω = ω 8 {\displaystyle \omega =\omega _{8}} is an eighth <a href="/facts/Root_of_unity/EqH0ho1Y">root of unity</a> satisfying ω 8 = ( e i 2 π 8 ) 8 = 1 {\displaystyle \omega ^{8}=\left(e^{\frac {i2\pi }{8}}\right)^{8}=1} . </p><p>The matrix representation of the Fourier transform on three qubits is: </p> F 8 = 1 8 [ 1 1 1 1 1 1 1 1 1 ω ω 2 ω 3 ω 4 ω 5 ω 6 ω 7 1 ω 2 ω 4 ω 6 1 ω 2 ω 4 ω 6 1 ω 3 ω 6 ω ω 4 ω 7 ω 2 ω 5 1 ω 4 1 ω 4 1 ω 4 1 ω 4 1 ω 5 ω 2 ω 7 ω 4 ω ω 6 ω 3 1 ω 6 ω 4 ω 2 1 ω 6 ω 4 ω 2 1 ω 7 ω 6 ω 5 ω 4 ω 3 ω 2 ω ] . {\displaystyle 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}}.} <p>The 3-qubit quantum Fourier transform can be rewritten as: </p> QFT ( | x 1 , x 2 , x 3 ⟩ ) = 1 8 ( | 0 ⟩ + e 2 π i [ 0. x 3 ] | 1 ⟩ ) ⊗ ( | 0 ⟩ + e 2 π i [ 0. x 2 x 3 ] | 1 ⟩ ) ⊗ ( | 0 ⟩ + e 2 π i [ 0. x 1 x 2 x 3 ] | 1 ⟩ ) . {\displaystyle {\text{QFT}}(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {8}}}\ \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).} <p>The following sketch shows the respective circuit for n = 3 {\displaystyle n=3} (with reversed order of output qubits with respect to the proper QFT): </p><p>As calculated above, the number of gates used is n ( n + 1 ) / 2 {\displaystyle n(n+1)/2} which is equal to 6 {\displaystyle 6} , for n = 3 {\displaystyle n=3} . </p> <h2 id="relation-to-quantum-hadamard-transform">Relation to quantum Hadamard transform</h2> <p class="note">See also: <a href="/facts/Hadamard_transform/JFD5uojA">Hadamard transform § Quantum computing applications</a></p> <p>Using the generalized <a href="/facts/Fourier_transform_on_finite_groups/6hg9lXsN">Fourier transform on finite (abelian) groups</a>, there are actually two natural ways to define a quantum Fourier transform on an <i>n</i>-qubit <a href="/facts/Quantum_register/SKE6E55m">quantum register</a>. The QFT as defined above is equivalent to the DFT, which considers these n qubits as indexed by the cyclic group Z / 2 n Z {\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} } . However, it also makes sense to consider the qubits as indexed by the <a href="/facts/Boolean_group/rWVah6P0">Boolean group</a> ( Z / 2 Z ) n {\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}} , and in this case the Fourier transform is the <a href="/facts/Hadamard_transform/JFD5uojA">Hadamard transform</a>. This is achieved by applying a <a href="/facts/Hadamard_gate/JFD5uojA">Hadamard gate</a> to each of the n qubits in parallel.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a><a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> <a href="/facts/Shor%2527s_algorithm/9JwEtznC">Shor's algorithm</a> uses both types of Fourier transforms, an initial Hadamard transform as well as a QFT. </p> <h2 id="for-other-groups">For other groups</h2> <p>The Fourier transform can be formulated for <a href="/facts/Fourier_transform_on_finite_groups/6hg9lXsN">groups other than the cyclic group</a>, and extended to the quantum setting.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> For example, consider the symmetric group S n {\displaystyle S_{n}} .<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a><a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> The Fourier transform can be expressed in matrix form </p> F n = ∑ λ ∈ Λ n ∑ p , q ∈ P ( λ ) ∑ g ∈ S n d λ n ! [ λ ( g ) ] q , p | λ , p , q ⟩ ⟨ g | , {\displaystyle {\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|,} <p>where [ λ ( g ) ] q , p {\displaystyle [\lambda (g)]_{q,p}} is the ( q , p ) {\displaystyle (q,p)} element of the matrix representation of λ ( g ) {\displaystyle \lambda (g)} , P ( λ ) {\displaystyle {\mathcal {P}}(\lambda )} is the set of paths from the root node to λ {\displaystyle \lambda } in the <a href="/facts/Bratteli_diagram/v1xcgGrr">Bratteli diagram</a> of S n {\displaystyle S_{n}} , Λ n {\displaystyle \Lambda _{n}} is the set of representations of S n {\displaystyle S_{n}} indexed by <a href="/facts/Young_diagram/e5lI4bck">Young diagrams</a>, and g {\displaystyle g} is a permutation. </p> <h2 id="over-a-finite-field">Over a finite field</h2> <p>The discrete Fourier transform can also be <a href="/facts/Discrete_Fourier_transform_over_a_ring/ntR67BjE">formulated over a finite field</a> F q {\displaystyle F_{q}} , and a quantum version can be defined.<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> Consider N = q = p n {\displaystyle N=q=p^{n}} . Let ϕ : G F ( q ) → G F ( p ) {\displaystyle \phi :GF(q)\to GF(p)} be an arbitrary linear map (trace, for example). Then for each x ∈ G F ( q ) {\displaystyle x\in GF(q)} define </p> F q , ϕ : | x ⟩ ↦ 1 q ∑ y ∈ G F ( q ) ω ϕ ( x y ) | y ⟩ {\displaystyle F_{q,\phi }:|x\rangle \mapsto {\frac {1}{\sqrt {q}}}\sum _{y\in GF(q)}\omega ^{\phi (xy)}|y\rangle } <p>for ω = e 2 π i / p {\displaystyle \omega =e^{2\pi i/p}} and extend F q , ϕ {\displaystyle F_{q,\phi }} linearly. </p> <h2 id="further-reading">Further reading</h2> <ul><li><a href="/facts/K._R._Parthasarathy_(probabilist)/fklWPEzG">Parthasarathy, K. R.</a> (2006). <i>Lectures on Quantum Computation, Quantum Error Correcting Codes and Information Theory</i>. Tata Institute of Fundamental Research. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-81-7319-688-1.</li> <li><a href="/facts/John_Preskill/6hdJUwhm">Preskill, John</a> (September 1998). <a href="https://web.gps.caltech.edu/~rls/book.pdf">"Lecture Notes for Physics 229: Quantum Information and Computation"</a> (PDF).</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://demonstrations.wolfram.com/QuantumCircuitImplementingGroversSearchAlgorithm/">Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm</a></li> <li><a href="http://demonstrations.wolfram.com/QuantumFourierTransformCircuit/">Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform</a></li> <li><a href="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</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Coppersmith, D. (2002). An approximate Fourier transform useful in quantum factoring (Preprint). arXiv:quant-ph/0201067. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Draper, Thomas G. (7 Aug 2000). "Addition on a Quantum Computer". arXiv:quant-ph/0008033. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Ruiz-Perez, Lidia; Juan Carlos, Garcia-Escartin (2 May 2017). "Quantum arithmetic with the quantum Fourier transform". Quantum Information Processing. 16 (6): 152. arXiv:1411.5949v2. Bibcode:2017QuIP...16..152R. doi:10.1007/s11128-017-1603-1. S2CID 10948948. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Şahin, Engin (2020). "Quantum arithmetic operations based on quantum Fourier transform on signed integers". International Journal of Quantum Information. 18 (6): 2050035. arXiv:2005.00443v3. Bibcode:2020IJQI...1850035S. doi:10.1142/s0219749920500355. ISSN 1793-6918. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Nielsen, Michael A.; Chuang, Isaac L. (2012). Quantum Computation and Quantum Information. doi:10.1017/CBO9780511976667. ISBN 978-1-107-00217-3. <a href="978-1-107-00217-3" target="_blank">978-1-107-00217-3</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Hales, L.; Hallgren, S. (November 12–14, 2000). "An improved quantum Fourier transform algorithm and applications". Proceedings 41st Annual Symposium on Foundations of Computer Science. pp. 515–525. CiteSeerX 10.1.1.29.4161. doi:10.1109/SFCS.2000.892139. ISBN 0-7695-0850-2. S2CID 424297. <a href="0-7695-0850-2" target="_blank">0-7695-0850-2</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Nielsen, Michael A.; Chuang, Isaac L. (2012). Quantum Computation and Quantum Information. doi:10.1017/CBO9780511976667. ISBN 978-1-107-00217-3. <a href="978-1-107-00217-3" target="_blank">978-1-107-00217-3</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Kurgalin, Sergei; Borzunov, Sergei (2021). Concise guide to quantum computing: algorithms, exercises, and implementations. Texts in computer science. Cham: Springer. ISBN 978-3-030-65054-4. <a href="978-3-030-65054-4" target="_blank">978-3-030-65054-4</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Fowler, A.G.; Devitt, S.J.; Hollenberg, L.C.L. (July 2004). "Implementation of Shor's algorithm on a linear nearest neighbour qubit array". Quantum Information and Computation. 4 (4): 237–251. doi:10.26421/QIC4.4-1. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Maslov, Dmitri (15 November 2007). "Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures". Physical Review A. 76 (5): 052310. arXiv:quant-ph/0703211. Bibcode:2007PhRvA..76e2310M. doi:10.1103/PhysRevA.76.052310. S2CID 18645435. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12-13[full citation needed] <a href="https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf" target="_blank">https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-5 <a href="https://web.archive.org/web/20210713134541/https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf" target="_blank">https://web.archive.org/web/20210713134541/https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Moore, Cristopher; Rockmore, Daniel; Russell, Alexander (2003). Generic Quantum Fourier Transforms (Preprint). arXiv:quant-ph/0304064. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Kawano, Yasuhito; Sekigawa, Hiroshi (July 2016). "Quantum Fourier transform over symmetric groups — improved result". Journal of Symbolic Computation. 75: 219–243. doi:10.1016/j.jsc.2015.11.016. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Beals, Robert (1997). "Quantum computation of Fourier transforms over symmetric groups". Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97. pp. 48–53. doi:10.1145/258533.258548. ISBN 0-89791-888-6. <a href="0-89791-888-6" target="_blank">0-89791-888-6</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>de Beaudrap, Niel; Cleve, Richard; Waltrous, John (8 November 2002). "Sharp Quantum versus Classical Query Complexity Separations". Algorithmica. 34 (4): 449–461. doi:10.1007/s00453-002-0978-1. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> </ol>