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.

Abbildung 1: QFT für 3 Qubits (ohne Umkehrung der Reihenfolge der Zustände der Ausgaben)

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}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)R_m=\left(\begin{array}{cc}1& 0\\ 0& {\zeta }_m\end{array}\right)$

Dabei bezeichnet ${\zeta }_m$ die $2^m$-te Einheitswurzel $e^{\frac{2\pi i}{2^m}}$.

Abbildung 2: QFT für n Qubits (ohne Umkehrung der Reihenfolge der Zustände der Ausgaben)

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⟩,|1⟩,\dots ,|N-1⟩$

Als diskrete Fouriertransformation bildet auch die Quanten-Fouriertransformation jeden Basiszustand $|x⟩$ auf eine Überlagerung aller Basiszustände ab:

${\mathrm{QFT}}_N|x⟩=\frac{1}{\sqrt{N}}\sum _{j=0}^{N-1}{\zeta }_n^{x\cdot j}|j⟩$

mit ${\zeta }_n=\exp \left(\frac{2\pi \mathrm{i}}{N}\right)$ der N-ten Einheitswurzel. Alternativ kann die Quanten-Fouriertransformation auch mittels der folgenden Faktorisierung berechnet werden:

${\mathrm{QFT}}_N|x⟩=\frac{1}{\sqrt{N}}\cdot (|0⟩+{\zeta }_1^x|1⟩)\otimes (|0⟩+{\zeta }_2^x|1⟩)\otimes (|0⟩+{\zeta }_3^x|1⟩)\otimes \cdots \otimes (|0⟩+{\zeta }_n^x|1⟩)$

Berechnet man sie mit Hilfe der Verallgemeinerung der obigen Quantenschaltkreis-Idee, erhält man fast die obige Faktorisierung, allerdings in umgekehrter Reihenfolge, konkret:

$|x⟩⟼\frac{1}{\sqrt{N}}\cdot (|0⟩+{\zeta }_n^x|1⟩)\otimes (|0⟩+{\zeta }_{n-1}^x|1⟩)\otimes (|0⟩+{\zeta }_{n-2}^x|1⟩)\otimes \cdots \otimes (|0⟩+{\zeta }_1^x|1⟩)$

Eigenschaften

Wendet man die Quanten-Fouriertransformation auf den Zustand $|0⟩$ an, so erzeugt sie genauso wie die Hadamard-Transformation eine gleichgewichtete Superposition der Basiszustände:

${\mathrm{QFT}}_N|0⟩={\mathrm{H}}_N|0⟩=\frac{1}{\sqrt{N}}\sum _{x=0}^{N-1}|x⟩$

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.
• Vorlage:Literatur
• 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.

Weblinks

• Alexandra Waldherr: Quantencomputer programmieren: Nur eine Phase? heise online 2. Dezember 2022