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 | Quelltext bearbeiten]

Am einfachsten wird die Struktur der Quanten-Fouriertransformation anhand des entsprechenden Quantenschaltkreises sichtbar. In der folgenden Skizze findet man ihn für mit (ohne Normierung und ohne die noch erforderliche Umkehrung der Reihenfolge der Zustände der Ausgaben).

QFT für 3 Qubits (ohne Normierung und ohne Umkehrung der Reihenfolge der Zustände der Ausgaben)

Der folgende Link zeigt die Situation für 1-, 2- und 3-Qubit-Register: Skizzen und Simulator für 1-, 2- und 3-Qubit-Register bei QFT

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

Dabei bezeichnet die -te Einheitswurzel .

Die Quanten-Fouriertransformation benötigt bei Qubits insgesamt Gatter für den entsprechenden Schaltkreis sowie weitere, um die Output-Qubits in die richtige Ordnung zu bringen.[1]

Mathematische Beschreibung[Bearbeiten | Quelltext bearbeiten]

In der Quanteninformatik werden Algorithmen durch ihre Wirkung auf ein Quantenregister beschrieben. Die Quanten-Fouriertransformation arbeitet auf einem Quantenregister mit Qubits, wobei dessen Basiszustände unter Verwendung der Bra-Ket-Notation folgendermaßen notiert werden:

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

Alternativ kann die Quanten-Fouriertransformation auch mittels der folgenden Faktorisierung berechnet werden:

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

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Wendet man die Quanten-Fouriertransformation auf den Zustand an, so erzeugt sie genauso wie die Hadamard-Transformation eine gleichgewichtete Superposition der Basiszustände:

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

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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