Quanten-Fouriertransformation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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.

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 R_m beschrifteten Gatter gesteuerte Phasengatter repräsentieren.

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 m-te Einheitswurzel e^{\frac{2 \pi i}{m}}.

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 |1\rangle steht (Controlled Phase).

Die Quanten-Fouriertransformation benötigt insgesamt O(n^2) Gatter:

\frac{n(n+1)}{2}

für den obigen Schaltkreis sowie O(n) weitere, um die Output-Qubits in die richtige Ordnung zu bringen.[1]

Mathematische Beschreibung[Bearbeiten]

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

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

\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[Bearbeiten]

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.

Einzelnachweise[Bearbeiten]

  1.  M. A. Nielsen und I. Chuang,: Quantum Computation and Quantum Information. Cambridge University Press, 2000, S. 219/220.