Quanten-Fouriertransformation

Algorithmus aus dem Gebiet der Quanteninformatik

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.

QuantenschaltkreisBearbeiten

Am einfachsten wird die Struktur der Quanten-Fouriertransformation anhand des entsprechenden Quantenschaltkreises sichtbar. In der folgenden Skizze findet man ihn für   (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.   usw.

 
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.[1]

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  .

Eine verallgemeinerte Schaltskizze ist in folgender Grafik 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.

 
QFT für n Qubits (ohne Umkehrung der Reihenfolge der Zustände der Ausgaben)

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.

Mathematische BeschreibungBearbeiten

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:

 

EigenschaftenBearbeiten

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.

Quellen und EinzelnachweiseBearbeiten

Allgemeine QuellenBearbeiten

  • M. Homeister: Quantum Computing verstehen. fünfte Auflage, Vieweg-Verlag, Wiesbaden 2018, ISBN 978-3-658-22883-5, S. 214ff.
  • B. Lenze: Mathematik und Quantum Computing. zweite Auflage, Logos Verlag, Berlin 2020, ISBN 978-3-8325-4716-5, S. 67ff.
  • M.A. Nielsen, I.L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge MA 2010, ISBN 978-1-107-00217-3, S. 216ff.
  • W. Scherer: Mathematik der Quanteninformatik. Springer-Verlag, Berlin/Heidelberg 2016, ISBN 978-3-662-49079-2, S. 180ff.
  • C.P. Williams: Explorations in Quantum Computing. zweite Auflage, Springer-Verlag, London 2011, ISBN 978-1-84628-886-9, S. 140ff.

EinzelnachweiseBearbeiten

  1. Quantum Fourier Transform Circuit (englisch) WOLFRAM TECHNOLOGIES. Abgerufen am 24. September 2019.