Quanten-Fouriertransformation
# Quanten-Fouriertransformation

Die Quanten-Fouriertransformation ist ein Algorithmus aus dem Gebiet der Quanteninformatik. Sie ist eine Zerlegung der diskreten Fouriertransformation in ein Produkt unitärer Matrizen. Dadurch kann sie als Quantenschaltkreis aus Hadamard-Gattern und Phasengattern implementiert werden.
Die Quanten-Fouriertransformation ist ein wesentlicher Bestandteil eines der prominentesten Quantenalgorithmen, des Shor-Algorithmus.

## Quantenschaltkreis

Am einfachsten wird die Struktur der Quanten-Fouriertransformation anhand des entsprechenden Quantenschaltkreises sichtbar. In Abbildung 1 findet man ihn für $n=3$ (ohne die noch erforderliche Umkehrung der Reihenfolge der Zustände der Ausgaben). Dort ist die übliche Notation für die binäre Darstellung der Phasenterme genutzt, d. h. $[0.x_{1}x_{2}\dots x_{n}]=x_{1}/2+x_{2}/4~+\dots +~x_{n}/2^{n}$ usw.
Die Situation für 1-, 2- und 3-Qubit-Register wird auf der Seite des Wolfram Demonstrations Project dargestellt.
Daran kann man leicht erkennen, wie die Schaltkreise für größere Quantenregister aussehen. Die mit $H$ beschrifteten Quantengatter stellen Hadamard-Gatter dar, während die mit $R_{m}$ beschrifteten Gatter Phasengatter repräsentieren, die hier als gesteuerte Gatter eingesetzt werden (Steuer-Qubit wie üblich durch schwarzen Punkt und Verbindungslinie zum Ziel-Qubit angedeutet; Controlled Phase).
Die einzelnen Gatter werden jeweils durch folgende unitäre Matrizen beschrieben.
    $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}}$
Dabei bezeichnet $\zeta _{m}$ die $2^{m}$-te Einheitswurzel $e^{\frac {2\pi i}{2^{m}}}$.
Eine verallgemeinerte Schaltskizze ist in Abbildung 2 zu sehen, wieder ohne die erforderliche Umkehrung der Reihenfolge der Ausgabe-Zustände. Hier ist wieder die binäre Darstellung in den Ausgabezuständen genutzt.
Die Quanten-Fouriertransformation benötigt bei $n$ Qubits insgesamt $O(n^{2})$ Gatter für den entsprechenden Schaltkreis sowie $O(n)$ weitere, um die Output-Qubits in die richtige Ordnung zu bringen.

## Mathematische Beschreibung

In der Quanteninformatik werden Algorithmen durch ihre Wirkung auf ein Quantenregister beschrieben. Die Quanten-Fouriertransformation arbeitet auf einem Quantenregister mit $n$ Qubits, wobei dessen $N=2^{n}$ Basiszustände unter Verwendung der Bra-Ket-Notation folgendermaßen notiert werden:
    $|0\rangle ,|1\rangle ,\ldots ,|N-1\rangle$
Als diskrete Fouriertransformation bildet auch die Quanten-Fouriertransformation jeden Basiszustand $|x\rangle$ auf eine Überlagerung aller Basiszustände ab:
    $\operatorname {QFT} _{N}|x\rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}\zeta _{n}^{x\cdot j}|j\rangle$
mit $\zeta _{n}=\exp \left({\tfrac {2\pi \mathrm {i} }{N}}\right)$ der N-ten Einheitswurzel. Alternativ kann die Quanten-Fouriertransformation auch mittels der folgenden Faktorisierung berechnet werden:
    $\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)$
Berechnet man sie mit Hilfe der Verallgemeinerung der obigen Quantenschaltkreis-Idee, erhält man fast die obige Faktorisierung, allerdings in umgekehrter Reihenfolge, konkret:
    $|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)$

## Eigenschaften

Wendet man die Quanten-Fouriertransformation auf den Zustand $|0\rangle$ an, so erzeugt sie genauso wie die Hadamard-Transformation eine gleichgewichtete Superposition der Basiszustände:
    $\operatorname {QFT} _{N}|0\rangle =\operatorname {H} _{N}|0\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle$
Des Weiteren besitzt die Quanten-Fouriertransformation natürlich auch alle Eigenschaften der diskreten Fouriertransformation.

## Quellen und Einzelnachweise
### Allgemeine Quellen

* M. Homeister: Quantum Computing verstehen. fünfte Auflage, Vieweg-Verlag, Wiesbaden 2018, ISBN 978-3-658-22883-5, S. 214ff.
* B. Lenze: Mathematik und Quantum Computing. zweite Auflage, Logos Verlag, Berlin 2020, ISBN 978-3-8325-4716-5, S. 67ff.
* M. A. Nielsen, I. L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge MA 2010, ISBN 978-1-107-00217-3, S. 216 ff. (wordpress.com [PDF]).
* W. Scherer: Mathematik der Quanteninformatik. Springer-Verlag, Berlin/Heidelberg 2016, ISBN 978-3-662-49079-2, S. 180ff.
* C.P. Williams: Explorations in Quantum Computing. zweite Auflage, Springer-Verlag, London 2011, ISBN 978-1-84628-886-9, S. 140ff.