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.x1x2…xn]=x1/2+x2/4 +⋯+ xn/2n 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 Rm 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=12(111−1)Rm=(100ζm)

Dabei bezeichnet ζm die 2m-te Einheitswurzel e2πi2m.

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(n2) 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=2n Basiszustände unter Verwendung der Bra-Ket-Notation folgendermaßen notiert werden:

|0⟩,|1⟩,…,|N−1⟩

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

QFTN|x⟩=1N∑j=0N−1ζnx⋅j|j⟩

mit ζn=exp⁡(2πiN) der N-ten Einheitswurzel. Alternativ kann die Quanten-Fouriertransformation auch mittels der folgenden Faktorisierung berechnet werden:

QFTN|x⟩=1N⋅(|0⟩+ζ1x|1⟩)⊗(|0⟩+ζ2x|1⟩)⊗(|0⟩+ζ3x|1⟩)⊗⋯⊗(|0⟩+ζnx|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⟩⟼1N⋅(|0⟩+ζnx|1⟩)⊗(|0⟩+ζn−1x|1⟩)⊗(|0⟩+ζn−2x|1⟩)⊗⋯⊗(|0⟩+ζ1x|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:

QFTN|0⟩=HN|0⟩=1N∑x=0N−1|x⟩

Des Weiteren besitzt die Quanten-Fouriertransformation natürlich auch alle Eigenschaften der diskreten Fouriertransformation.

Quellen und Einzelnachweise

Allgemeine Quellen