Quantum Fourier transform

Last updated July 03, 2024

In quantum computing, the quantum Fourier transform (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 was discovered by Don Coppersmith.^[2] With small modifications to the QFT, it can also be used for performing fast integer arithmetic operations such as addition and multiplication.^[3]^[4]

The quantum Fourier transform can be performed efficiently on a quantum computer with a decomposition into the product of simpler unitary matrices. 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.^[5] 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})$ .

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 quantum case it is a sequence of probability amplitudes for all the possible outcomes upon measurement (the outcomes are the basis states, or eigenstates ). Because measurement 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 (as of late 2000) require only $O(n\log n)$ gates to achieve an efficient approximation, provided that a controlled phase gate is implemented as a native operation.^[6]

Definition

The quantum Fourier transform is the classical discrete Fourier transform applied to the vector of amplitudes of a quantum state, which usually has 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 _{n=0}^{N-1}x_{n}\omega _{N}^{-nk},\quad k=0,1,2,\ldots ,N-1,

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

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

y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk},\quad k=0,1,2,\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 vice versa.)

Since $\omega _{N}^{n}$ is a rotation, the inverse quantum Fourier transform acts similarly but with:

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

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

{\text{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 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 &&\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}}

where $\omega =\omega _{N}$ . For example, in the case of $N=4=2^{2}$ and phase $\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}}

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 $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.

Circuit implementation

The quantum gates used in the circuit of $n$ qubits are the Hadamard gate and the phase gate $R_{k}$ :

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

The circuit is composed of $H$ gates and the controlled version of $R_{k}$ :

An orthonormal basis consists of the basis states

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

These basis states span all 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$ 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_{i}\rangle =\left({\frac {1}{\sqrt {2}}}\right)\left(|0\rangle +e^{2\pi ix_{i}2^{-1}}|1\rangle \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}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.

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

{\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).

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.^[5]

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)+\cdots +1=n(n+1)/2=O(n^{2})$ gates, which is quadratic polynomial in the number of qubits.

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

Example

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

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

where $\omega =\omega _{8}$ is an eighth root of unity satisfying $\omega ^{8}=\left(e^{\frac {i2\pi }{8}}\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:

{\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).

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

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

Relation to quantum Hadamard transform

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 $\mathbb {Z} /2^{n}\mathbb {Z}$ . However, it also makes sense to consider the qubits as indexed by the Boolean group $(\mathbb {Z} /2\mathbb {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.^[9]^[10] 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 groups other than the cyclic group, and extended to the quantum setting.^[11] For example, consider the symmetric group $S_{n}$ .^[12]^[13] The Fourier transform can be expressed in matrix form

${\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|$

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

Over a finite field

The discrete Fourier transform can also be formulated over a finite field $F_{q}$ , and a quantum version can be defined.^[14] Here $N=q=p^{n}$ . Let $\phi :GF(q)\rightarrow GF(p)$ be an arbitrary linear map (trace, for example). Then for each $x\in GF(q)$ define

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

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

Related Research Articles

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

<span class="mw-page-title-main">Quantum harmonic oscillator</span> Important, well-understood quantum mechanical model

The quantum harmonic oscillator is the quantum-mechanical analog of the classical harmonic oscillator. Because an arbitrary smooth potential can usually be approximated as a harmonic potential at the vicinity of a stable equilibrium point, it is one of the most important model systems in quantum mechanics. Furthermore, it is one of the few quantum-mechanical systems for which an exact, analytical solution is known.

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just $evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.$

Quantum superposition is a fundamental principle of quantum mechanics that states that linear combinations of solutions to the Schrödinger equation are also solutions of the Schrödinger equation. This follows from the fact that the Schrödinger equation is a linear differential equation in time and position. More precisely, the state of a system is given by a linear combination of all the eigenfunctions of the Schrödinger equation governing that system.

The Hadamard transform is an example of a generalized class of Fourier transforms. It performs an orthogonal, symmetric, involutive, linear operation on $2 m$ real numbers.

Creation operators and annihilation operators are mathematical operators that have widespread applications in quantum mechanics, notably in the study of quantum harmonic oscillators and many-particle systems. An annihilation operator lowers the number of particles in a given state by one. A creation operator increases the number of particles in a given state by one, and it is the adjoint of the annihilation operator. In many subfields of physics and chemistry, the use of these operators instead of wavefunctions is known as second quantization. They were introduced by Paul Dirac.

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. Quantum logic gates are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

In quantum information theory, superdense coding is a quantum communication protocol to communicate a number of classical bits of information by only transmitting a smaller number of qubits, under the assumption of sender and receiver pre-sharing an entangled resource. In its simplest form, the protocol involves two parties, often referred to as Alice and Bob in this context, which share a pair of maximally entangled qubits, and allows Alice to transmit two bits to Bob by sending only one qubit. This protocol was first proposed by Charles H. Bennett and Stephen Wiesner in 1970 and experimentally actualized in 1996 by Klaus Mattle, Harald Weinfurter, Paul G. Kwiat and Anton Zeilinger using entangled photon pairs. Superdense coding can be thought of as the opposite of quantum teleportation, in which one transfers one qubit from Alice to Bob by communicating two classical bits, as long as Alice and Bob have a pre-shared Bell pair.

<span class="mw-page-title-main">Controlled NOT gate</span> Quantum logic gate

In computer science, the controlled NOT gate, controlled-X gate, controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a quantum logic gate that is an essential component in the construction of a gate-based quantum computer. It can be used to entangle and disentangle Bell states. Any quantum circuit can be simulated to an arbitrary degree of accuracy using a combination of CNOT gates and single qubit rotations. The gate is sometimes named after Richard Feynman who developed an early notation for quantum gate diagrams in 1986.

<span class="mw-page-title-main">LOCC</span> Method in quantum computation and communication

LOCC, or local operations and classical communication, is a method in quantum information theory where a local (product) operation is performed on part of the system, and where the result of that operation is "communicated" classically to another part where usually another local operation is performed conditioned on the information received.

In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error.

In mathematics and physics, in particular quantum information, the term generalized Pauli matrices refers to families of matrices which generalize the properties of the Pauli matrices. Here, a few classes of such matrices are summarized.

In quantum mechanics, notably in quantum information theory, fidelity quantifies the "closeness" between two density matrices. It expresses the probability that one state will pass a test to identify as the other. It is not a metric on the space of density matrices, but it can be used to define the Bures metric on this space.

In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.

The quantization of the electromagnetic field means that an electromagnetic field consists of discrete energy parcels called photons. Photons are massless particles of definite energy, definite momentum, and definite spin.

In quantum computing, the quantum phase estimation algorithm is a quantum algorithm to estimate the phase corresponding to an eigenvalue of a given unitary operator. Because the eigenvalues of a unitary operator always have unit modulus, they are characterized by their phase, and therefore the algorithm can be equivalently described as retrieving either the phase or the eigenvalue itself. The algorithm was initially introduced by Alexei Kitaev in 1995.

Circuit quantum electrodynamics provides a means of studying the fundamental interaction between light and matter. As in the field of cavity quantum electrodynamics, a single photon within a single mode cavity coherently couples to a quantum object (atom). In contrast to cavity QED, the photon is stored in a one-dimensional on-chip resonator and the quantum object is no natural atom but an artificial one. These artificial atoms usually are mesoscopic devices which exhibit an atom-like energy spectrum. The field of circuit QED is a prominent example for quantum information processing and a promising candidate for future quantum computation.

Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.

In quantum computing, Mølmer–Sørensen gate scheme refers to an implementation procedure for various multi-qubit quantum logic gates used mostly in trapped ion quantum computing. This procedure is based on the original proposition by Klaus Mølmer and Anders Sørensen in 1999-2000.

The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1997. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.

References

↑ "Quantum Fourier Transformation in Industrial Applications".
↑ Coppersmith, D. (2002). An approximate Fourier transform useful in quantum factoring (Preprint). arXiv: quant-ph/0201067 .
↑ Draper, Thomas G. (7 Aug 2000). "Addition on a Quantum Computer". arXiv: quant-ph/0008033 .
↑ 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.
1 2 Nielsen, Michael A.; Chuang, Isaac L. (2012). Quantum Computation and Quantum Information. doi:10.1017/CBO9780511976667. ISBN 978-1-107-00217-3.
↑ 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.
↑ 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.
↑ 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.
↑ Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12-13 ^{[ full citation needed ]}
↑ Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-5 ^{[ dead link ]}
↑ Moore, Cristopher; Rockmore, Daniel; Russell, Alexander (2003). Generic Quantum Fourier Transforms (Preprint). arXiv: quant-ph/0304064 .
↑ 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.
↑ 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.
↑ 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.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "Quantum Fourier Transformation in Industrial Applications".

[dc_qft-2] Coppersmith, D. (2002). An approximate Fourier transform useful in quantum factoring (Preprint). arXiv: quant-ph/0201067 .

[3] Draper, Thomas G. (7 Aug 2000). "Addition on a Quantum Computer". arXiv: quant-ph/0008033 .

[4] 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.

[:0-5] 1 2 Nielsen, Michael A.; Chuang, Isaac L. (2012). Quantum Computation and Quantum Information. doi:10.1017/CBO9780511976667. ISBN 978-1-107-00217-3.

[6] 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.

[7] 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.

[8] 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.

[9] Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12-13 ^{[ full citation needed ]}

[10] Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-5 ^{[ dead link ]}

[11] Moore, Cristopher; Rockmore, Daniel; Russell, Alexander (2003). Generic Quantum Fourier Transforms (Preprint). arXiv: quant-ph/0304064 .

[12] 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.

[13] 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.

[14] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]