Quanten-Fouriertransformation – Wikipedia

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.

Am einfachsten wird die Struktur der Quanten-Fouriertransformation anhand des entsprechenden Quantenschaltkreises sichtbar. In der folgenden Skizze findet man ihn für

{displaystyle n=3}

$n=3$ (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.

{displaystyle [0.x_{1}x_{2}…x_{n}]=x_{1}/2+x_{2}/4~+…+~x_{n}/2^{n}}

${displaystyle [0.x_{1}x_{2}...x_{n}]=x_{1}/2+x_{2}/4~+...+~x_{n}/2^{n}}$ 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

{displaystyle H}

$H$ beschrifteten Quantengatter stellen Hadamard-Gatter dar, während die mit

{displaystyle R_{m}}

$R_{m}$ 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.

{displaystyle H={frac {1}{sqrt {2}}}{begin{pmatrix}1&1\1&-1end{pmatrix}}quad R_{m}={begin{pmatrix}1&0\0&zeta _{m}end{pmatrix}}}

Dabei bezeichnet

{displaystyle zeta _{m}}

$zeta _{m}$ die

{displaystyle 2^{m}}

$2^m$ -te Einheitswurzel

{displaystyle e^{frac {2pi i}{2^{m}}}}

${displaystyle e^{frac {2pi i}{2^{m}}}}$ .

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

{displaystyle n}

$n$ Qubits insgesamt

{displaystyle O(n^{2})}

$O(n^2)$ Gatter
für den entsprechenden Schaltkreis sowie

{displaystyle O(n)}

$O(n)$ weitere, um die Output-Qubits in die richtige Ordnung zu bringen.

In der Quanteninformatik werden Algorithmen durch ihre Wirkung auf ein Quantenregister beschrieben. Die Quanten-Fouriertransformation arbeitet auf einem Quantenregister mit

{displaystyle n}

$n$ Qubits, wobei dessen

{displaystyle N=2^{n}}

$N=2^{n}$ Basiszustände unter Verwendung der Bra-Ket-Notation folgendermaßen notiert werden:

{displaystyle |0rangle ,|1rangle ,ldots ,|N-1rangle }

Als diskrete Fouriertransformation bildet auch die Quanten-Fouriertransformation jeden Basiszustand

{displaystyle |xrangle }

$|xrangle$ auf eine Überlagerung aller Basiszustände ab:

{displaystyle operatorname {QFT} _{N}|xrangle ={frac {1}{sqrt {N}}}sum _{j=0}^{N-1}zeta _{n}^{xcdot j}|jrangle }

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

{displaystyle operatorname {QFT} _{N}|xrangle ={frac {1}{sqrt {N}}}cdot left(|0rangle +zeta _{1}^{x}|1rangle right)otimes left(|0rangle +zeta _{2}^{x}|1rangle right)otimes left(|0rangle +zeta _{3}^{x}|1rangle right)otimes cdots otimes left(|0rangle +zeta _{n}^{x}|1rangle right)}

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

{displaystyle |xrangle longmapsto {frac {1}{sqrt {N}}}cdot left(|0rangle +zeta _{n}^{x}|1rangle right)otimes left(|0rangle +zeta _{n-1}^{x}|1rangle right)otimes left(|0rangle +zeta _{n-2}^{x}|1rangle right)otimes cdots otimes left(|0rangle +zeta _{1}^{x}|1rangle right)}

Wendet man die Quanten-Fouriertransformation auf den Zustand

{displaystyle |0rangle }

$|0rangle$ an, so erzeugt sie genauso wie die Hadamard-Transformation eine gleichgewichtete Superposition der Basiszustände:

{displaystyle operatorname {QFT} _{N}|0rangle =operatorname {H} _{N}|0rangle ={frac {1}{sqrt {N}}}sum _{x=0}^{N-1}|xrangle }

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

Allgemeine Quellen[Bearbeiten | Quelltext bearbeiten]

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.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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

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

Quanten-Fouriertransformation – Wikipedia

Allgemeine Quellen[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

Recent Posts

Recent Comments

Archives

Categories

Meta