Quantum Fourier Transform

The quantum Fourier transform is an algorithm from the field of quantum informatics . It is a decomposition of the discrete Fourier transform into a product of unitary matrices . This allows it to be implemented as a quantum circuit made up of Hadamard gates and phase gates .

The quantum Fourier transform is an essential part of one of the most prominent quantum algorithms , the Shor algorithm .

Quantum circuit

The easiest way to see the structure of the quantum Fourier transform is to use the corresponding quantum circuit. It can be found in the following sketch for (without the still required reversal of the order of the states of the outputs). There the usual notation is used for the binary representation of the phase terms, i. H. etc. ${\displaystyle n=3}$ ${\displaystyle [0.x_{1}x_{2}...x_{n}]=x_{1}/2+x_{2}/4~+...+~x_{n}/2^{n}}$

QFT for 3 qubits (without reversing the order of the states of the outputs)

The situation for 1, 2 and 3 qubit registers is presented on the Wolfram Demonstrations Project website.

This makes it easy to see what the circuits for larger quantum registers look like. The quantum gates labeled with represent Hadamard gates, while the gates labeled with represent phase gates that are used here as controlled gates (control qubit, as usual, indicated by a black dot and a connecting line to the target qubit; controlled phase). ${\displaystyle H}$ ${\displaystyle R_{m}}$

The individual gates are each described by the following unitary matrices .

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\quad R_{m}={\begin{pmatrix}1&0\\0&\zeta _{m}\end{pmatrix}}}$

The -th denotes the root of unity . ${\displaystyle \zeta _{m}}$ ${\displaystyle 2^{m}}$ ${\displaystyle e^{\frac {2\pi i}{2^{m}}}}$

A generalized circuit diagram can be seen in the following graphic, again without the necessary reversal of the order of the output states. Here again the binary representation is used in the output states.

QFT for n qubits (without reversing the order of the states of the outputs)

In the case of qubits, the quantum Fourier transform requires gates for the corresponding circuit as well as additional gates in order to bring the output qubits into the correct order. ${\displaystyle n}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n)}$

Mathematical description

In quantum informatics, algorithms are described by their effect on a quantum register. The quantum Fourier transform works on a quantum register with qubits, whereby its base states are noted using the Bra-Ket notation as follows: ${\displaystyle n}$ ${\displaystyle N=2^{n}}$

${\displaystyle |0\rangle ,|1\rangle ,\ldots ,|N-1\rangle }$

As a discrete Fourier transformation, the quantum Fourier transformation also maps each base state onto a superposition of all base states: ${\displaystyle |x\rangle }$

${\displaystyle \operatorname {QFT} _{N}|x\rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}\zeta _{n}^{x\cdot j}|j\rangle }$

Alternatively, the quantum Fourier transform can also be calculated using the following factorization:

${\displaystyle \operatorname {QFT} _{N}|x\rangle ={\frac {1}{\sqrt {N}}}\cdot \left(|0\rangle +\zeta _{1}^{x}|1\rangle \right)\otimes \left(|0\rangle +\zeta _{2}^{x}|1\rangle \right)\otimes \left(|0\rangle +\zeta _{3}^{x}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +\zeta _{n}^{x}|1\rangle \right)}$

If you calculate it with the help of the generalization of the above quantum circuit idea, you get almost the above factorization, but in reverse order, specifically:

${\displaystyle |x\rangle \longmapsto {\frac {1}{\sqrt {N}}}\cdot \left(|0\rangle +\zeta _{n}^{x}|1\rangle \right)\otimes \left(|0\rangle +\zeta _{n-1}^{x}|1\rangle \right)\otimes \left(|0\rangle +\zeta _{n-2}^{x}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +\zeta _{1}^{x}|1\rangle \right)}$

properties

If the quantum Fourier transform is applied to the state , it generates, just like the Hadamard transform, an equally weighted superposition of the base states: ${\displaystyle |0\rangle }$

${\displaystyle \operatorname {QFT} _{N}|0\rangle =\operatorname {H} _{N}|0\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle }$

Furthermore, the quantum Fourier transform naturally also has all the properties of the discrete Fourier transform.

Sources and individual references

1. ↑ Quantum Fourier Transform Circuit ( English ) WOLFRAM TECHNOLOGIES. Retrieved September 24, 2019.

• M. Homeister: Understanding Quantum Computing. Vieweg-Verlag, Wiesbaden 2018, fifth edition, ISBN 978-3-6582-2883-5 , p. 214ff.
• B. Lenze: Mathematik und Quantum Computing Logos Verlag, Berlin 2020, second edition, ISBN 978-3-8325-4716-5 , p. 67ff.
• MA Nielsen, IL Chuang: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge MA 2010, ISBN 978-1-1070-0217-3 , pp. 216ff.
• W. Scherer: Mathematics of Quanteninformatik Springer-Verlag, Berlin-Heidelberg 2016, ISBN 978-3-6624-9079-2 , p. 180ff.
• CP Williams: Explorations in Quantum Computing Springer-Verlag, London 2011, second edition, ISBN 978-1-8462-8886-9 , pp. 140ff.