www.wikidata.de-de.nina.az

Quanten Fouriertransformation Die ist ein Algorithmus aus dem Gebiet der Quanteninformatik Sie ist eine Zerlegung der di

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.

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

Quantenschaltkreis Bearbeiten

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.

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 Beschreibung 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:

mit der N-ten Einheitswurzel. 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

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 Einzelnachweise Bearbeiten

Allgemeine Quellen 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. 216 ff. (wordpress.com [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 Bearbeiten

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

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Quanten Fouriertransformation ist ein Algorithmus aus dem Gebiet der Quanteninformatik Sie ist eine Zerlegung der diskreten Fouriertransformation in ein Produkt unitarer 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 Inhaltsverzeichnis 1 Quantenschaltkreis 2 Mathematische Beschreibung 3 Eigenschaften 4 Quellen und Einzelnachweise 4 1 Allgemeine Quellen 4 2 Einzelnachweise 5 WeblinksQuantenschaltkreis BearbeitenAm einfachsten wird die Struktur der Quanten Fouriertransformation anhand des entsprechenden Quantenschaltkreises sichtbar In der folgenden Skizze findet man ihn fur n 3 displaystyle n 3 nbsp ohne die noch erforderliche Umkehrung der Reihenfolge der Zustande der Ausgaben Dort ist die ubliche Notation fur die binare Darstellung der Phasenterme genutzt d h 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 nbsp usw nbsp QFT fur 3 Qubits ohne Umkehrung der Reihenfolge der Zustande der Ausgaben Die Situation fur 1 2 und 3 Qubit Register wird auf der Seite des Wolfram Demonstrations Project dargestellt 1 Daran kann man leicht erkennen wie die Schaltkreise fur grossere Quantenregister aussehen Die mit H displaystyle H nbsp beschrifteten Quantengatter stellen Hadamard Gatter dar wahrend die mit R m displaystyle R m nbsp beschrifteten Gatter Phasengatter reprasentieren die hier als gesteuerte Gatter eingesetzt werden Steuer Qubit wie ublich durch schwarzen Punkt und Verbindungslinie zum Ziel Qubit angedeutet Controlled Phase Die einzelnen Gatter werden jeweils durch folgende unitare Matrizen beschrieben H 1 2 1 1 1 1 R m 1 0 0 z m displaystyle H frac 1 sqrt 2 begin pmatrix 1 amp 1 1 amp 1 end pmatrix quad R m begin pmatrix 1 amp 0 0 amp zeta m end pmatrix nbsp Dabei bezeichnet z m displaystyle zeta m nbsp die 2 m displaystyle 2 m nbsp te Einheitswurzel e 2 p i 2 m displaystyle e frac 2 pi i 2 m nbsp Eine verallgemeinerte Schaltskizze ist in folgender Grafik zu sehen wieder ohne die erforderliche Umkehrung der Reihenfolge der Ausgabe Zustande Hier ist wieder die binare Darstellung in den Ausgabezustanden genutzt nbsp QFT fur n Qubits ohne Umkehrung der Reihenfolge der Zustande der Ausgaben Die Quanten Fouriertransformation benotigt bei n displaystyle n nbsp Qubits insgesamt O n 2 displaystyle O n 2 nbsp Gatter fur den entsprechenden Schaltkreis sowie O n displaystyle O n nbsp weitere um die Output Qubits in die richtige Ordnung zu bringen Mathematische Beschreibung BearbeitenIn der Quanteninformatik werden Algorithmen durch ihre Wirkung auf ein Quantenregister beschrieben Die Quanten Fouriertransformation arbeitet auf einem Quantenregister mit n displaystyle n nbsp Qubits wobei dessen N 2 n displaystyle N 2 n nbsp Basiszustande unter Verwendung der Bra Ket Notation folgendermassen notiert werden 0 1 N 1 displaystyle 0 rangle 1 rangle ldots N 1 rangle nbsp Als diskrete Fouriertransformation bildet auch die Quanten Fouriertransformation jeden Basiszustand x displaystyle x rangle nbsp auf eine Uberlagerung aller Basiszustande ab QFT N x 1 N j 0 N 1 z n x j j displaystyle operatorname QFT N x rangle frac 1 sqrt N sum j 0 N 1 zeta n x cdot j j rangle nbsp mit z n exp 2 p i N displaystyle zeta n exp frac 2 pi mathrm i N nbsp der N ten Einheitswurzel Alternativ kann die Quanten Fouriertransformation auch mittels der folgenden Faktorisierung berechnet werden QFT N x 1 N 0 z 1 x 1 0 z 2 x 1 0 z 3 x 1 0 z n x 1 displaystyle 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 nbsp Berechnet man sie mit Hilfe der Verallgemeinerung der obigen Quantenschaltkreis Idee erhalt man fast die obige Faktorisierung allerdings in umgekehrter Reihenfolge konkret x 1 N 0 z n x 1 0 z n 1 x 1 0 z n 2 x 1 0 z 1 x 1 displaystyle 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 nbsp Eigenschaften BearbeitenWendet man die Quanten Fouriertransformation auf den Zustand 0 displaystyle 0 rangle nbsp an so erzeugt sie genauso wie die Hadamard Transformation eine gleichgewichtete Superposition der Basiszustande QFT N 0 H N 0 1 N x 0 N 1 x displaystyle operatorname QFT N 0 rangle operatorname H N 0 rangle frac 1 sqrt N sum x 0 N 1 x rangle nbsp Des Weiteren besitzt die Quanten Fouriertransformation naturlich auch alle Eigenschaften der diskreten Fouriertransformation Quellen und Einzelnachweise BearbeitenAllgemeine Quellen Bearbeiten M Homeister Quantum Computing verstehen funfte 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 216 ff wordpress com 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 Bearbeiten Quantum Fourier Transform Circuit WOLFRAM TECHNOLOGIES abgerufen am 24 September 2019 englisch Weblinks BearbeitenAlexandra Waldherr Quantencomputer programmieren Nur eine Phase heise online 2 Dezember 2022 Abgerufen von https de wikipedia org w index php title Quanten Fouriertransformation amp oldid 239409698