Meine Merkliste

Home
Lexikon
Quanten-Fouriertransformation

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.

Weiteres empfehlenswertes Fachwissen

Erkennen Sie die Auswirkungen elektrostatischer Aufladungen auf Ihre Waage

Wie kann man Pipetten schnell überprüfen?

Leitfaden für die Waagenreinigung: 8 einfache Schritte

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 Qubit bestehendes Quantenregister.

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_i = \begin{pmatrix} 1 & 0 \\ 0 & \zeta_m \end{pmatrix}$

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

Die Quanten-Fouriertransformation benötigt insgesamt

$\frac{n(n-1)}{2} = O(n^2)$

Gatter.

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 \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

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.

Kategorie: Quanteninformatik

Dieser Artikel basiert auf dem Artikel Quanten-Fouriertransformation aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar.