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, dem Shor-Algorithmus.

Quantenschaltkreis

Am einfachsten wird die Struktur der Quanten-Fouriertransformation anhand des entsprechenden Quantenschaltkreises sichtbar. Das folgende Bild zeigt den Quantenschaltkreis für ein aus drei Qubits bestehendes Quantenregister.

Datei:Quantum Fourier transform on three qubits.svg

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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): R_m beschrifteten Gatter gesteuerte Phasengatter repräsentieren.

Die einzelnen Gatter werden jeweils durch folgende unitäre Matrizen beschrieben.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \zeta_m die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): m -te Einheitswurzel $ e^{\frac {2\pi i}{m}} $.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): R_m ist eigentlich eine 2-Qubit-Operation, wird hier aber als 1-Qubit-Operation für das zweite Qubit beschrieben, die nur aktiviert wird, wenn das erste Qubit auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): |1\rangle steht (Controlled Phase).

Die Quanten-Fouriertransformation benötigt insgesamt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): O(n^2) Gatter:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \frac{n(n+1)}{2}

für den obigen Schaltkreis sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): O(n) weitere, um die Output-Qubits in die richtige Ordnung zu bringen.^[1]

Mathematische Beschreibung

In der Quanteninformatik werden Algorithmen durch ihre Wirkung auf ein Quantenregister beschrieben. Die Quanten-Fouriertransformation arbeitet auf einem Quantenregister mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): n Qubits, wobei dessen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): | x \rangle auf eine Überlagerung aller Basiszustände ab:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{QFT}_N | x \rangle = \frac{1}{\sqrt N} \sum_{j=0}^{N - 1} \zeta_N^{x \cdot j} | j \rangle

Als Quanten-Fouriertransformation bezeichnet man die folgende Faktorisierung der obigen Gleichung:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): \operatorname{QFT}_N | x \rangle = \frac{1}{\sqrt N} \cdot \left( | 0 \rangle + \zeta_2^x | 1 \rangle \right) \cdot \left( | 0 \rangle + \zeta_4^x | 1 \rangle \right) \cdot \left( | 0 \rangle + \zeta_8^x | 1 \rangle \right) \cdot \ldots \cdot \left( | 0 \rangle + \zeta_N^x | 1 \rangle \right)

Eigenschaften

Wendet man die Quanten-Fouriertransformation auf den Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): | 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.

Einzelnachweise