imported>Boehm: typog, abb

2024-10-02T10:34:50Z

typog, abb

Neue Seite

Die '''Quanten-Fouriertransformation''' ist ein [[Algorithmus]] aus dem Gebiet der [[Quanteninformatik]]. Sie ist eine Zerlegung der [[Diskrete Fourier-Transformation|diskreten Fouriertransformation]] in ein Produkt [[Unitäre Matrix|unitärer Matrizen]]. Dadurch kann sie als [[Quantenschaltkreis]] aus [[Hadamard-Gatter]]n und [[Allgemeines Phasengatter|Phasengattern]] implementiert werden.

Die Quanten-Fouriertransformation ist ein wesentlicher Bestandteil eines der prominentesten [[Quantenalgorithmus|Quantenalgorithmen]], des [[Shor-Algorithmus]].

== Quantenschaltkreis ==

Am einfachsten wird die Struktur der Quanten-Fouriertransformation anhand des entsprechenden Quantenschaltkreises sichtbar. In Abbildung 1 findet man ihn für <math>n=3</math> (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. <math>[0.x_1x_2 \dots x_n] = x_1/2 + x_2/4~+ \dots +~x_n/2^{n}</math> usw.

[[Datei:Q fourier 3qubits.png|700px|mini|Abbildung 1: 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.<ref>{{cite web | url=https://demonstrations.wolfram.com/QuantumFourierTransformCircuit/ | title=Quantum Fourier Transform Circuit | publisher=WOLFRAM TECHNOLOGIES | language=englisch | accessdate=2019-09-24}}</ref>

Daran kann man leicht erkennen, wie die Schaltkreise für größere Quantenregister aussehen. Die mit <math>H</math> beschrifteten [[Quantengatter]] stellen Hadamard-Gatter dar, während die mit <math>R_m</math> 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 Matrix|unitäre Matrizen]] beschrieben.
:<math>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}</math>
Dabei bezeichnet <math>\zeta_m</math> die <math>2^m</math>-te [[Einheitswurzel]] <math>e^{\frac{2 \pi i}{2^m}}</math>.

[[Datei: Q fourier nqubits.png|700px|mini|Abbildung 2: QFT für n Qubits (ohne Umkehrung der Reihenfolge der Zustände der Ausgaben)]]
Eine verallgemeinerte Schaltskizze ist in Abbildung 2 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.

Die Quanten-Fouriertransformation benötigt bei <math>n</math> Qubits insgesamt <math>O(n^2)</math> Gatter
für den entsprechenden Schaltkreis sowie <math>O(n)</math> weitere, um die Output-Qubits in die richtige Ordnung zu bringen.

== Mathematische Beschreibung ==

In der Quanteninformatik werden Algorithmen durch ihre Wirkung auf ein Quantenregister beschrieben. Die Quanten-Fouriertransformation arbeitet auf einem Quantenregister mit <math>n</math> Qubits, wobei dessen <math>N = 2^n</math> Basiszustände unter Verwendung der [[Bra-Ket]]-Notation folgendermaßen notiert werden:
:<math>| 0 \rangle , | 1 \rangle , \ldots, | N - 1 \rangle</math>
Als diskrete Fouriertransformation bildet auch die Quanten-Fouriertransformation jeden Basiszustand <math>| x \rangle</math> auf eine Überlagerung aller Basiszustände ab:
:<math>\operatorname{QFT}_N | x \rangle = \frac{1}{\sqrt N} \sum_{j=0}^{N - 1} \zeta_n^{x \cdot j} | j \rangle</math>
mit <math>\zeta_n = \exp\left(\tfrac{2\pi \mathrm i}{N}\right)</math> der N-ten [[Einheitswurzel]].
Alternativ kann die Quanten-Fouriertransformation auch mittels der folgenden Faktorisierung berechnet werden:
:<math> \operatorname{QFT}_N | x \rangle = \frac{1}{\sqrt N} \cdot \left( | 0 \rangle + \zeta_1^x | 1 \rangle \right) \otimes \left( | 0 \rangle + \zeta_2^x | 1 \rangle \right) \otimes \left( | 0 \rangle + \zeta_3^x | 1 \rangle \right) \otimes \cdots \otimes \left( | 0 \rangle + \zeta_n^x | 1 \rangle \right)</math>
Berechnet man sie mit Hilfe der Verallgemeinerung der obigen Quantenschaltkreis-Idee, erhält man fast die obige Faktorisierung, allerdings in umgekehrter Reihenfolge, konkret:
:<math> | x \rangle \longmapsto \frac{1}{\sqrt N} \cdot \left( | 0 \rangle + \zeta_n^x | 1 \rangle \right) \otimes \left( | 0 \rangle + \zeta_{n-1}^x | 1 \rangle \right) \otimes \left( | 0 \rangle + \zeta_{n-2}^x | 1 \rangle \right) \otimes \cdots \otimes \left( | 0 \rangle + \zeta_1^x | 1 \rangle \right)</math>

== Eigenschaften ==

Wendet man die Quanten-Fouriertransformation auf den Zustand <math>| 0 \rangle</math> an, so erzeugt sie genauso wie die [[Hadamard-Transformation]] eine gleichgewichtete [[Superposition (Physik)|Superposition]] der Basiszustände:
:<math>\operatorname{QFT}_N | 0 \rangle = \operatorname{H}_N | 0 \rangle = \frac{1}{\sqrt N} \sum_{x=0}^{N - 1} | x \rangle</math>

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

== Quellen und Einzelnachweise ==
=== Allgemeine Quellen ===
* 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.
* {{Literatur|Autor=[[Michael Nielsen|M. A. Nielsen]], [[Isaac Chuang|I. L. Chuang]]|Titel= Quantum Computation and Quantum Information. |Verlag = Cambridge University Press|Ort= Cambridge MA| Datum = 2010|ISBN = 978-1-107-00217-3| Seiten= 216ff|Online =https://profmcruz.files.wordpress.com/2017/08/quantum-computation-and-quantum-information-nielsen-chuang.pdf }}
* 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 ===
<references />

== Weblinks ==
* Alexandra Waldherr: [https://www.heise.de/hintergrund/Quantencomputer-programmieren-Nur-eine-Phase-7358148.html ''Quantencomputer programmieren: Nur eine Phase?''] [[heise online]] 2. Dezember 2022

[[Kategorie:Quanteninformatik]]
[[Kategorie:Diskrete Transformation]]

Quanten-Fouriertransformation - Versionsgeschichte

imported>Boehm: typog, abb