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 <math>n=3</math> (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. <math>[0.x_1x_2 \dots x_n] = x_1/2 + x_2/4~+ \dots +~x_n/2^{n}</math> usw.

Datei:Q fourier 3qubits.png

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.<ref>Vorlage:Cite book/Name: [Internetquelle: archiv-url ungültig Quantum Fourier Transform Circuit.] WOLFRAM TECHNOLOGIES, , archiviert vom Vorlage:IconExternal (nicht mehr online verfügbar) am Vorlage:Cite book/URL; abgerufen am 24. September 2019 (englisch). Vorlage:Cite book/URL Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung2 Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung Vorlage:Cite book/Meldung</ref>

Daran kann man leicht erkennen, wie die Schaltkreise für größere Quantenregister aussehen. Die mit <math>H</math> beschrifteten Quantengatter stellen Hadamard-Gatter dar, während die mit <math>R_m</math> 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.

<math>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}</math> Dabei bezeichnet <math>\zeta_m</math> die <math>2^m</math>-te Einheitswurzel <math>e^{\frac{2 \pi i}{2^m}}</math>.

Datei:Q fourier nqubits.png

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 <math>n</math> Qubits insgesamt <math>O(n^2)</math> Gatter für den entsprechenden Schaltkreis sowie <math>O(n)</math> 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 <math>n</math> Qubits, wobei dessen <math>N = 2^n</math> Basiszustände unter Verwendung der Bra-Ket-Notation folgendermaßen notiert werden:

<math>| 0 \rangle , | 1 \rangle , \ldots, | N - 1 \rangle</math>

Als diskrete Fouriertransformation bildet auch die Quanten-Fouriertransformation jeden Basiszustand <math>| x \rangle</math> auf eine Überlagerung aller Basiszustände ab:

<math>\operatorname{QFT}_N | x \rangle = \frac{1}{\sqrt N} \sum_{j=0}^{N - 1} \zeta_n^{x \cdot j} | j \rangle</math>

mit <math>\zeta_n = \exp\left(\tfrac{2\pi \mathrm i}{N}\right)</math> der N-ten Einheitswurzel. Alternativ kann die Quanten-Fouriertransformation auch mittels der folgenden Faktorisierung berechnet werden:

<math> \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)</math>

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

<math> | 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)</math>

Eigenschaften

Wendet man die Quanten-Fouriertransformation auf den Zustand <math>| 0 \rangle</math> an, so erzeugt sie genauso wie die Hadamard-Transformation eine gleichgewichtete Superposition der Basiszustände:

<math>\operatorname{QFT}_N | 0 \rangle = \operatorname{H}_N | 0 \rangle = \frac{1}{\sqrt N} \sum_{x=0}^{N - 1} | x \rangle</math>

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.

Einzelnachweise

Weblinks

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