[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/wiki46\/2022\/01\/13\/quanten-fouriertransformation-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/wiki46\/2022\/01\/13\/quanten-fouriertransformation-wikipedia\/","headline":"Quanten-Fouriertransformation \u2013 Wikipedia","name":"Quanten-Fouriertransformation \u2013 Wikipedia","description":"Die Quanten-Fouriertransformation ist ein Algorithmus aus dem Gebiet der Quanteninformatik. Sie ist eine Zerlegung der diskreten Fouriertransformation in ein Produkt","datePublished":"2022-01-13","dateModified":"2022-01-13","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/wiki46\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/wiki46\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/1c5a5a42ced00df920fad4ab2d4acdb960a4105b","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/1c5a5a42ced00df920fad4ab2d4acdb960a4105b","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/wiki46\/2022\/01\/13\/quanten-fouriertransformation-wikipedia\/","wordCount":4284,"articleBody":"Die Quanten-Fouriertransformation ist ein Algorithmus aus dem Gebiet der Quanteninformatik. Sie ist eine Zerlegung der diskreten Fouriertransformation in ein Produkt unit\u00e4rer 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\u00fcr n=3{displaystyle n=3} (ohne die noch erforderliche Umkehrung der Reihenfolge der Zust\u00e4nde der Ausgaben). Dort ist die \u00fcbliche Notation f\u00fcr die bin\u00e4re Darstellung der Phasenterme genutzt, d.\u00a0h.   [0.x1x2...xn]=x1\/2+x2\/4\u00a0+...+\u00a0xn\/2n{displaystyle [0.x_{1}x_{2}…x_{n}]=x_{1}\/2+x_{2}\/4~+…+~x_{n}\/2^{n}} usw.  QFT f\u00fcr 3 Qubits (ohne Umkehrung der Reihenfolge der Zust\u00e4nde der Ausgaben)Die Situation f\u00fcr 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\u00fcr gr\u00f6\u00dfere Quantenregister aussehen. Die mit   H{displaystyle H} beschrifteten Quantengatter stellen Hadamard-Gatter dar, w\u00e4hrend die mit Rm{displaystyle R_{m}} beschrifteten Gatter Phasengatter repr\u00e4sentieren, die hier als gesteuerte Gatter eingesetzt werden (Steuer-Qubit wie \u00fcblich durch schwarzen Punkt und Verbindungslinie zum Ziel-Qubit angedeutet; Controlled Phase).Die einzelnen Gatter werden jeweils durch folgende unit\u00e4re Matrizen beschrieben.H=12(111\u22121)Rm=(100\u03b6m){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 \u03b6m{displaystyle zeta _{m}} die 2m{displaystyle 2^{m}}-te Einheitswurzel e2\u03c0i2m{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\u00e4nde. Hier ist wieder die bin\u00e4re Darstellung in den Ausgabezust\u00e4nden genutzt.  QFT f\u00fcr n Qubits (ohne Umkehrung der Reihenfolge der Zust\u00e4nde der Ausgaben)Die Quanten-Fouriertransformation ben\u00f6tigt bei n{displaystyle n} Qubits insgesamt O(n2){displaystyle O(n^{2})} Gatterf\u00fcr den entsprechenden Schaltkreis sowie O(n){displaystyle 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 n{displaystyle n} Qubits, wobei dessen N=2n{displaystyle N=2^{n}} Basiszust\u00e4nde unter Verwendung der Bra-Ket-Notation folgenderma\u00dfen notiert werden:|0\u27e9,|1\u27e9,\u2026,|N\u22121\u27e9{displaystyle |0rangle ,|1rangle ,ldots ,|N-1rangle }Als diskrete Fouriertransformation bildet auch die Quanten-Fouriertransformation jeden Basiszustand |x\u27e9{displaystyle |xrangle } auf eine \u00dcberlagerung aller Basiszust\u00e4nde ab:QFTN\u2061|x\u27e9=1N\u2211j=0N\u22121\u03b6nx\u22c5j|j\u27e9{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:QFTN\u2061|x\u27e9=1N\u22c5(|0\u27e9+\u03b61x|1\u27e9)\u2297(|0\u27e9+\u03b62x|1\u27e9)\u2297(|0\u27e9+\u03b63x|1\u27e9)\u2297\u22ef\u2297(|0\u27e9+\u03b6nx|1\u27e9){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\u00e4lt man fast die obige Faktorisierung, allerdings in umgekehrter Reihenfolge, konkret:|x\u27e9\u27fc1N\u22c5(|0\u27e9+\u03b6nx|1\u27e9)\u2297(|0\u27e9+\u03b6n\u22121x|1\u27e9)\u2297(|0\u27e9+\u03b6n\u22122x|1\u27e9)\u2297\u22ef\u2297(|0\u27e9+\u03b61x|1\u27e9){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 |0\u27e9{displaystyle |0rangle } an, so erzeugt sie genauso wie die Hadamard-Transformation eine gleichgewichtete Superposition der Basiszust\u00e4nde:QFTN\u2061|0\u27e9=HN\u2061|0\u27e9=1N\u2211x=0N\u22121|x\u27e9{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\u00fcrlich auch alle Eigenschaften der diskreten Fouriertransformation.Allgemeine Quellen[Bearbeiten | Quelltext bearbeiten]M. Homeister: Quantum Computing verstehen. f\u00fcnfte 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]\u2191 Quantum Fourier Transform Circuit (englisch) WOLFRAM TECHNOLOGIES. Abgerufen am 24.\u00a0September 2019."},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki46\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/wiki46\/2022\/01\/13\/quanten-fouriertransformation-wikipedia\/#breadcrumbitem","name":"Quanten-Fouriertransformation \u2013 Wikipedia"}}]}]