www.wikidata.de-de.nina.az

Deutsch Jozsa Algorithmus Der Algorithmus von Deutsch ist ein Quantenalgorithmus für Quantencomputer mit dem man bestimm

Deutsch-Jozsa-Algorithmus

Der Algorithmus von Deutsch ist ein Quantenalgorithmus für Quantencomputer, mit dem man bestimmen kann, ob eine auf einem Bit operierende Funktion konstant oder balanciert ist. Diese Aufgabenstellung ist unter dem Namen Problem von Deutsch bekannt. Der Algorithmus von Deutsch ist zwar kaum von praktischem Nutzen, er war jedoch historisch der erste Quantenalgorithmus, der eine Aufgabenstellung nachweisbar schneller löst als ein klassischer Algorithmus und damit die theoretischen Möglichkeiten von Quantencomputern aufzeigt.

Eine Verallgemeinerung ist der Deutsch-Jozsa-Algorithmus. Dabei wird das Problem von Deutsch auf mehrere Bits übertragen.

Die Algorithmen wurden nach ihren Urhebern David Deutsch und Richard Jozsa benannt.

Geschichte Bearbeiten

In einer Arbeit von 1985 beschäftigte sich David Deutsch mit dem Spezialfall des Problems (Problem von Deutsch, Anzahl der Eingabebits: 1).

1992 wurde die Idee durch David Deutsch und Richard Jozsa verallgemeinert (Problem von Deutsch-Jozsa, beliebig viele Eingabebits).

Der von Deutsch ursprünglich vorgeschlagene Algorithmus war de facto nicht deterministisch. Er war mit einer Wahrscheinlichkeit von 0,5 erfolgreich. Der originale Deutsch-Jozsa-Algorithmus war zwar deterministisch, benötigte jedoch im Gegensatz zum Algorithmus von Deutsch zwei Funktionsauswertungen statt nur einer.

Durch R. Cleve, A. Ekert, C. Macchiavello und M. Mosca wurden 1998 weitere Verbesserungen vorgenommen, so dass jetzt nur noch eine Funktionsauswertung benötigt wird und der Algorithmus dennoch deterministisch bleibt.

Der Deutsch-Jozsa-Algorithmus diente als Inspiration für den Shor-Algorithmus und den Grover-Algorithmus, zwei der revolutionärsten Quantenalgorithmen.

Das Problem von Deutsch Bearbeiten

Problemformulierung Bearbeiten

Gegeben sei eine Funktion . Es gilt nun herauszufinden, ob die gegebene Funktion konstant ist () oder balanciert/gleichgewichtet (). Dabei ist zu beachten, dass nur als Black Box gegeben ist, die genaue Definition also unbekannt ist – es steht lediglich ein Bauteil zur Verfügung, welches zu einem Bit den Wert berechnet. Um die Bedeutung des Algorithmus von Deutsch zu unterstreichen, sollte davon ausgegangen werden, dass die Benutzung dieses Bauteils teuer ist.

Zur Veranschaulichung kann man sich vorstellen, dass man entscheiden soll, ob eine gegebene Münze fair (Kopf auf der einen Seite, Zahl auf der anderen) oder unfair (Kopf oder Zahl auf beiden Seiten der Münze) ist.

Klassische Lösung Bearbeiten

Auf klassischem Wege bleibt nichts weiter übrig als die Funktion sowohl für als auch auszuwerten und zu vergleichen. Das entspricht dem Betrachten einer Münze auf beiden Seiten. Die Black Box (oder auch Orakel) wird also zweimal benötigt. Im Folgenden wird gezeigt, dass der Quantenalgorithmus von Deutsch mit nur einem Aufruf auskommt. Dies bringt einen Vorteil, wenn man bedenkt, dass nach der Annahme ein Aufruf sehr teuer ist (jedoch sind die Kosten asymptotisch gleich).

Der Quantenalgorithmus Bearbeiten

Quantenschaltung, die den Algorithmus von Deutsch implementiert

Der Quantenalgorithmus wendet die gegebene Funktion auf eine Superposition der beiden möglichen Eingaben an. Durch geschickte Auswertung erhält er somit mit nur einmaliger Anwendung des Orakels ausreichend Information über und .

Da in der Quanteninformatik alle Rechenschritte umkehrbar sein müssen, wird hier eine spezielle Variante von benötigt, unter Verwendung von (Addition mit anschließendem Modulo 2) beschrieben durch die Abbildung

Der Algorithmus verwendet ein Register von zwei Qubits (mit dem Tensorprodukt, welches gewöhnlich mit dargestellt wird) und besteht aus folgenden Schritten:

  1. Initialisiere wie folgt:
  2. Wende die Hadamard-Transformation auf beide Qubits an:
  3. Werte aus:
  4. Wende die Hadamard-Transformation auf das erste Qubit an:
  5. Miss das erste Qubit:

Der Trick besteht also darin, dass wir die Funktionswerte in die Amplitude verlagern.

Realisierung Bearbeiten

Über die erste experimentelle Realisierung wurde von S. Gulde in Nature 421, 48 (2003) berichtet. Die dafür benötigten Qubits wurden durch den elektronischen und vibratorischen Freiheitsgrad eines -Ions in einer Falle implementiert.

Das Problem von Deutsch-Jozsa Bearbeiten

Problemformulierung Bearbeiten

Nun wird die Funktion auf Eingabebits verallgemeinert: Es wird zugesichert, dass die Funktion entweder konstant (alle Eingaben werden auf ein und denselben Wert abgebildet) oder balanciert (die Hälfte der Eingaben wird auf und die andere Hälfte auf abgebildet) ist. Herauszufinden ist nun, welche der beiden Alternativen zutrifft. Erneut ist zu beachten, dass nur als Black Box bzw. Orakel gegeben ist.

Klassische Lösung Bearbeiten

Ein klassischer Computer müsste die Funktion im schlimmsten Fall für mehr als die Hälfte aller möglichen Eingaben auswerten, denn es kann passieren, dass selbst bei noch so geschickter Wahl die ersten (halb so viel wie insgesamt möglich) getesteten Eingaben beispielsweise zum Wert führen und somit noch nicht entscheidbar ist, welche Alternative gilt. Ergibt auch die nächste Auswertung , so ist die Funktion konstant, ergibt sie hingegen , ist sie balanciert.

Ein klassischer Algorithmus benötigt also im worst case Auswertungen von . Wie im Folgenden gezeigt wird, benötigt der Algorithmus von Deutsch-Jozsa nur eine einzige Auswertung. Dies stellt einen exponentiellen Laufzeitgewinn dar, was im Gegensatz zum Problem / Algorithmus von Deutsch eine echte Verbesserung der Komplexität ist.

Der Quantenalgorithmus Bearbeiten

Quantenschaltung, die den Algorithmus von Deutsch-Jozsa implementiert

Der Quantenalgorithmus wendet die gegebene Funktion auf eine Superposition aller möglichen Eingaben an. Durch geschickte Auswertung erhält er somit mit nur einmaliger Anwendung des Orakels ausreichend Information über alle Funktionswerte.

Auf Grund der zu erhaltenden Umkehrbarkeit wird wieder eine spezielle Variante von benötigt, beschrieben durch die Abbildung

wobei die Eingabe der Länge ist.

Der Algorithmus benutzt Qubits und durchläuft folgende Schritte:

  1. Initialisierung: die ersten Bits auf und das letzte Bit auf setzen:
  2. Wende die Hadamard-Transformation (also auf alle Qubits) an:
  3. Werte aus:
  4. Wende die Hadamard-Transformation auf an:
  5. Miss das Register :

Die Interpretation des Messergebnisses ist folgendermaßen einzusehen: Ist balanciert, so gleichen sich die Vorzeichen für aus, so dass mit einer Wahrscheinlichkeit von der Wert gemessen wird. Im anderen Fall, also wenn konstant ist, sind genau die Amplituden für gleich , da sich für solche die immer so einteilen lassen, dass die Hälfte skalarmultipliziert mit einen geraden Wert ergibt, die andere Hälfte aber einen ungeraden.

Alternativ kann auch die Tatsache genutzt werden, dass selbstadjungiert ist. Die Wahrscheinlichkeit zu messen ist das Betragsquadrat des Skalarproduktes

wobei die Hadamard-Transformation nach links angewendet wurde. Ist balanciert, so heben sich in der die positiven und negativen Beiträge weg, wohingegen sie sich im konstanten Fall aufsummieren.

Einzelnachweise Bearbeiten

  1. David Deutsch: The Church-Turing principle and the universal quantum computer. In: Proceedings of the Royal Society of London A. 400. Jahrgang, 1985, S. 97, doi:10.1098/rspa.1985.0070 (royalsocietypublishing.org [PDF]).
  2. David Deutsch und Richard Jozsa: Rapid solutions of problems by quantum computation. In: Proceedings of the Royal Society of London A. 439. Jahrgang, 1992, S. 553, doi:10.1098/rspa.1992.0167 (royalsocietypublishing.org [PDF]).
  3. R. Cleve, A. Ekert, C. Macchiavello und M. Mosca: Quantum algorithms revisited. In: Proceedings of the Royal Society of London A. 454. Jahrgang, 1998, S. 339–354, doi:10.1098/rspa.1998.0164, arxiv:quant-ph/9708016 (royalsocietypublishing.org [PDF]).
  4. Lov K. Grover: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. 1996, S. 212–219, doi:10.1145/237814.237866, arxiv:quant-ph/9605043.
  5. Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM J. Sci. Statist. Comput. 26. Jahrgang, 1997, S. 1484, doi:10.1137/S0097539795293172, arxiv:quant-ph/9508027 (siam.org [PDF]).

Literatur Bearbeiten

  • M. Homeister: Quantum Computing verstehen Springer Vieweg, Wiesbaden 2018, fünfte Auflage, ISBN 978-3-658-22883-5, S. 62ff.
  • B. Lenze: Mathematik und Quantum Computing Logos Verlag, Berlin 2020, zweite Auflage, ISBN 978-3-8325-4716-5, S. 51ff.
  • R.J. Lipton, K.W. Regan: Quantum Algorithms via Linear Algebra: A Primer MIT Press, Cambridge MA 2014, ISBN 978-0-262-02839-4, S. 77ff.
  • M.A. Nielsen, I.L. Chuang: Quantum Computation and Quantum Information Cambridge University Press, Cambridge MA 2010, ISBN 978-1-107-00217-3, S. 32ff.
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:
Der Algorithmus von Deutsch ist ein Quantenalgorithmus fur Quantencomputer mit dem man bestimmen kann ob eine auf einem Bit operierende Funktion konstant oder balanciert ist Diese Aufgabenstellung ist unter dem Namen Problem von Deutsch bekannt Der Algorithmus von Deutsch ist zwar kaum von praktischem Nutzen er war jedoch historisch der erste Quantenalgorithmus der eine Aufgabenstellung nachweisbar schneller lost als ein klassischer Algorithmus und damit die theoretischen Moglichkeiten von Quantencomputern aufzeigt Eine Verallgemeinerung ist der Deutsch Jozsa Algorithmus Dabei wird das Problem von Deutsch auf mehrere Bits ubertragen Die Algorithmen wurden nach ihren Urhebern David Deutsch und Richard Jozsa benannt Inhaltsverzeichnis 1 Geschichte 2 Das Problem von Deutsch 2 1 Problemformulierung 2 2 Klassische Losung 2 3 Der Quantenalgorithmus 2 4 Realisierung 3 Das Problem von Deutsch Jozsa 3 1 Problemformulierung 3 2 Klassische Losung 3 3 Der Quantenalgorithmus 4 Einzelnachweise 5 LiteraturGeschichte BearbeitenIn einer Arbeit von 1985 beschaftigte sich David Deutsch mit dem Spezialfall des Problems Problem von Deutsch Anzahl der Eingabebits 1 1 1992 wurde die Idee durch David Deutsch und Richard Jozsa verallgemeinert Problem von Deutsch Jozsa beliebig viele Eingabebits 2 Der von Deutsch ursprunglich vorgeschlagene Algorithmus war de facto nicht deterministisch Er war mit einer Wahrscheinlichkeit von 0 5 erfolgreich Der originale Deutsch Jozsa Algorithmus war zwar deterministisch benotigte jedoch im Gegensatz zum Algorithmus von Deutsch zwei Funktionsauswertungen statt nur einer Durch R Cleve A Ekert C Macchiavello und M Mosca wurden 1998 weitere Verbesserungen vorgenommen so dass jetzt nur noch eine Funktionsauswertung benotigt wird und der Algorithmus dennoch deterministisch bleibt 3 Der Deutsch Jozsa Algorithmus diente als Inspiration fur den Shor Algorithmus und den Grover Algorithmus zwei der revolutionarsten Quantenalgorithmen 4 5 Das Problem von Deutsch BearbeitenProblemformulierung Bearbeiten Gegeben sei eine Funktion f 0 1 0 1 displaystyle f lbrace 0 1 rbrace to lbrace 0 1 rbrace nbsp Es gilt nun herauszufinden ob die gegebene Funktion konstant ist f 0 f 1 displaystyle f 0 f 1 nbsp oder balanciert gleichgewichtet f 0 f 1 displaystyle f 0 neq f 1 nbsp Dabei ist zu beachten dass f displaystyle f nbsp nur als Black Box gegeben ist die genaue Definition also unbekannt ist es steht lediglich ein Bauteil zur Verfugung welches zu einem Bit b displaystyle b nbsp den Wert f b displaystyle f b nbsp berechnet Um die Bedeutung des Algorithmus von Deutsch zu unterstreichen sollte davon ausgegangen werden dass die Benutzung dieses Bauteils teuer ist Zur Veranschaulichung kann man sich vorstellen dass man entscheiden soll ob eine gegebene Munze fair Kopf auf der einen Seite Zahl auf der anderen oder unfair Kopf oder Zahl auf beiden Seiten der Munze ist Klassische Losung Bearbeiten Auf klassischem Wege bleibt nichts weiter ubrig als die Funktion sowohl fur f 0 displaystyle f 0 nbsp als auch f 1 displaystyle f 1 nbsp auszuwerten und zu vergleichen Das entspricht dem Betrachten einer Munze auf beiden Seiten Die Black Box oder auch Orakel wird also zweimal benotigt Im Folgenden wird gezeigt dass der Quantenalgorithmus von Deutsch mit nur einem Aufruf auskommt Dies bringt einen Vorteil wenn man bedenkt dass nach der Annahme ein Aufruf sehr teuer ist jedoch sind die Kosten asymptotisch gleich Der Quantenalgorithmus Bearbeiten nbsp Quantenschaltung die den Algorithmus von Deutsch implementiertDer Quantenalgorithmus wendet die gegebene Funktion auf eine Superposition der beiden moglichen Eingaben an Durch geschickte Auswertung erhalt er somit mit nur einmaliger Anwendung des Orakels ausreichend Information uber f 0 displaystyle f 0 nbsp und f 1 displaystyle f 1 nbsp Da in der Quanteninformatik alle Rechenschritte umkehrbar sein mussen wird hier eine spezielle Variante von f displaystyle f nbsp benotigt unter Verwendung von displaystyle oplus nbsp Addition mit anschliessendem Modulo 2 beschrieben durch die Abbildung U f x y x f x y displaystyle U f left x right rangle left y right rangle mapsto left x right rangle left f x oplus y right rangle nbsp Der Algorithmus verwendet ein Register von zwei Qubits x y displaystyle left x right rangle cdot left y right rangle nbsp mit displaystyle cdot nbsp dem Tensorprodukt welches gewohnlich mit displaystyle otimes nbsp dargestellt wird und besteht aus folgenden Schritten Initialisiere wie folgt x y 0 1 a displaystyle begin aligned left x right rangle left y right rangle amp left 0 right rangle left 1 right rangle amp left a right rangle end aligned nbsp Wende die Hadamard Transformation H displaystyle H nbsp auf beide Qubits an x y H x H y 1 2 0 1 1 2 0 1 1 2 0 0 0 1 1 0 1 1 b displaystyle begin aligned left x right rangle left y right rangle amp rightarrow H left x right rangle H left y right rangle amp frac 1 sqrt 2 bigl left 0 right rangle left 1 right rangle bigr cdot frac 1 sqrt 2 bigl left 0 right rangle left 1 right rangle bigr amp frac 1 2 bigl left 0 right rangle left 0 right rangle left 0 right rangle left 1 right rangle left 1 right rangle left 0 right rangle left 1 right rangle left 1 right rangle bigr amp left b right rangle end aligned nbsp Werte U f displaystyle U f nbsp aus x y U f x y 1 2 0 0 f 0 0 1 f 0 1 0 f 1 1 1 f 1 1 2 0 f 0 1 f 0 1 f 1 1 f 1 1 2 1 f 0 0 0 1 1 f 1 1 0 1 1 2 1 f 0 0 1 f 1 1 0 1 c displaystyle begin aligned left x right rangle left y right rangle amp rightarrow U f left x right rangle left y right rangle amp frac 1 2 Bigl left 0 right rangle left 0 oplus f 0 right rangle left 0 right rangle left 1 oplus f 0 right rangle left 1 right rangle left 0 oplus f 1 right rangle left 1 right rangle left 1 oplus f 1 right rangle Bigr amp frac 1 2 Bigl left 0 right rangle cdot bigl left f 0 right rangle left 1 oplus f 0 right rangle bigr left 1 right rangle cdot bigl left f 1 right rangle left 1 oplus f 1 right rangle bigr Bigr amp frac 1 2 Bigl 1 f 0 left 0 right rangle cdot bigl left 0 right rangle left 1 right rangle bigr 1 f 1 left 1 right rangle cdot bigl left 0 right rangle left 1 right rangle bigr Bigr amp frac 1 2 bigl 1 f 0 left 0 right rangle 1 f 1 left 1 right rangle bigr cdot bigl left 0 right rangle left 1 right rangle bigr amp left c right rangle end aligned nbsp c displaystyle left c right rangle nbsp ist im konstanten Fall 1 2 0 1 0 1 displaystyle frac 1 2 Bigl pm bigl left 0 right rangle left 1 right rangle bigr Bigr cdot bigl left 0 right rangle left 1 right rangle bigr nbsp und sonst 1 2 0 1 0 1 displaystyle frac 1 2 Bigl pm bigl left 0 right rangle left 1 right rangle bigr Bigr cdot bigl left 0 right rangle left 1 right rangle bigr nbsp Wende die Hadamard Transformation H displaystyle H nbsp auf das erste Qubit an x H x displaystyle left x right rangle rightarrow H left x right rangle nbsp Miss das erste Qubit Hat x displaystyle left x right rangle nbsp den Wert 0 displaystyle left 0 right rangle nbsp so ist f displaystyle f nbsp konstant ansonsten balanciert Der Trick besteht also darin dass wir die Funktionswerte in die Amplitude verlagern Realisierung Bearbeiten Uber die erste experimentelle Realisierung wurde von S Gulde in Nature 421 48 2003 berichtet Die dafur benotigten Qubits wurden durch den elektronischen und vibratorischen Freiheitsgrad eines C a displaystyle Ca nbsp Ions in einer Falle implementiert Das Problem von Deutsch Jozsa BearbeitenProblemformulierung Bearbeiten Nun wird die Funktion f displaystyle f nbsp auf n displaystyle n nbsp Eingabebits verallgemeinert f 0 1 n 0 1 displaystyle f lbrace 0 1 rbrace n to lbrace 0 1 rbrace nbsp Es wird zugesichert dass die Funktion entweder konstant alle Eingaben werden auf ein und denselben Wert abgebildet oder balanciert die Halfte der Eingaben wird auf 0 displaystyle 0 nbsp und die andere Halfte auf 1 displaystyle 1 nbsp abgebildet ist Herauszufinden ist nun welche der beiden Alternativen zutrifft Erneut ist zu beachten dass f displaystyle f nbsp nur als Black Box bzw Orakel gegeben ist Klassische Losung Bearbeiten Ein klassischer Computer musste die Funktion im schlimmsten Fall fur mehr als die Halfte aller moglichen Eingaben auswerten denn es kann passieren dass selbst bei noch so geschickter Wahl die ersten 2 n 1 displaystyle 2 n 1 nbsp halb so viel wie insgesamt moglich getesteten Eingaben beispielsweise zum Wert 0 displaystyle 0 nbsp fuhren und somit noch nicht entscheidbar ist welche Alternative gilt Ergibt auch die nachste Auswertung 0 displaystyle 0 nbsp so ist die Funktion konstant ergibt sie hingegen 1 displaystyle 1 nbsp ist sie balanciert Ein klassischer Algorithmus benotigt also im worst case 2 n 1 1 displaystyle 2 n 1 1 nbsp Auswertungen von f displaystyle f nbsp Wie im Folgenden gezeigt wird benotigt der Algorithmus von Deutsch Jozsa nur eine einzige Auswertung Dies stellt einen exponentiellen Laufzeitgewinn dar was im Gegensatz zum Problem Algorithmus von Deutsch eine echte Verbesserung der Komplexitat ist Der Quantenalgorithmus Bearbeiten nbsp Quantenschaltung die den Algorithmus von Deutsch Jozsa implementiertDer Quantenalgorithmus wendet die gegebene Funktion auf eine Superposition aller moglichen Eingaben an Durch geschickte Auswertung erhalt er somit mit nur einmaliger Anwendung des Orakels ausreichend Information uber alle Funktionswerte Auf Grund der zu erhaltenden Umkehrbarkeit wird wieder eine spezielle Variante von f displaystyle f nbsp benotigt beschrieben durch die Abbildung U f x y x f x y displaystyle U f left x right rangle left y right rangle mapsto left x right rangle left f x oplus y right rangle nbsp wobei x displaystyle left x right rangle nbsp die Eingabe der Lange n displaystyle n nbsp ist Der Algorithmus benutzt n 1 displaystyle n 1 nbsp Qubits und durchlauft folgende Schritte Initialisierung die ersten n displaystyle n nbsp Bits auf 0 displaystyle left 0 right rangle nbsp und das letzte Bit auf 1 displaystyle left 1 right rangle nbsp setzen x y 0 n 1 a displaystyle begin aligned left x right rangle left y right rangle amp left 0 right rangle otimes n left 1 right rangle amp left a right rangle end aligned nbsp Wende die Hadamard Transformation H n 1 displaystyle H n 1 nbsp also H 2 displaystyle H 2 nbsp auf alle Qubits an x y H n 1 x y 1 2 n x 0 2 n 1 x 1 2 0 1 1 2 n 1 x 0 2 n 1 x 0 1 b displaystyle begin aligned left x right rangle left y right rangle amp rightarrow H n 1 left x right rangle left y right rangle amp left frac 1 sqrt 2 n sum x 0 2 n 1 left x right rangle right cdot frac 1 sqrt 2 bigl left 0 right rangle left 1 right rangle bigr amp frac 1 sqrt 2 n 1 sum x 0 2 n 1 left x right rangle bigl left 0 right rangle left 1 right rangle bigr amp left b right rangle end aligned nbsp Werte U f displaystyle U f nbsp aus x y U f x y 1 2 n 1 x 0 2 n 1 x f x 1 f x 1 2 n 1 x 0 2 n 1 1 f x x 0 1 1 2 n x 0 2 n 1 1 f x x 1 2 0 1 c displaystyle begin aligned left x right rangle left y right rangle amp rightarrow U f left x right rangle left y right rangle amp frac 1 sqrt 2 n 1 sum x 0 2 n 1 left x right rangle bigl left f x right rangle left 1 oplus f x right rangle bigr amp frac 1 sqrt 2 n 1 sum x 0 2 n 1 1 f x left x right rangle bigl left 0 right rangle left 1 right rangle bigr amp left frac 1 sqrt 2 n sum x 0 2 n 1 1 f x left x right rangle right cdot frac 1 sqrt 2 bigl left 0 right rangle left 1 right rangle bigr amp left c right rangle end aligned nbsp Wende die Hadamard Transformation auf x displaystyle left x right rangle nbsp an x y H n x y 1 2 n z 0 2 n 1 x 0 2 n 1 1 x z f x z 1 2 0 1 d displaystyle begin aligned left x right rangle left y right rangle amp rightarrow bigl H n left x right rangle bigr left y right rangle amp left frac 1 2 n sum z 0 2 n 1 sum x 0 2 n 1 1 vec x cdot vec z f x left z right rangle right cdot frac 1 sqrt 2 bigl left 0 right rangle left 1 right rangle bigr amp left d right rangle end aligned nbsp Miss das Register x displaystyle left x right rangle nbsp Ist es 0 0 displaystyle left 0 ldots 0 right rangle nbsp so ist f displaystyle f nbsp konstant ansonsten balanciert Die Interpretation des Messergebnisses ist folgendermassen einzusehen Ist f displaystyle f nbsp balanciert so gleichen sich die Vorzeichen fur z 0 displaystyle left z right rangle left 0 right rangle nbsp aus so dass mit einer Wahrscheinlichkeit von 0 displaystyle 0 nbsp der Wert 0 displaystyle left 0 right rangle nbsp gemessen wird Im anderen Fall also wenn f displaystyle f nbsp konstant ist sind genau die Amplituden fur z 0 displaystyle left z right rangle neq left 0 right rangle nbsp gleich 0 displaystyle 0 nbsp da sich fur solche z displaystyle z nbsp die x displaystyle x nbsp immer so einteilen lassen dass die Halfte skalarmultipliziert mit z displaystyle z nbsp einen geraden Wert ergibt die andere Halfte aber einen ungeraden Alternativ kann auch die Tatsache genutzt werden dass H n displaystyle H n nbsp selbstadjungiert ist Die Wahrscheinlichkeit 0 0 displaystyle 0 ldots 0 rangle nbsp zu messen ist das Betragsquadrat des Skalarproduktes1 2 n 0 H n x 0 2 n 1 1 f x x 1 2 n x 0 z 0 2 n 1 z 1 f x x 1 2 n z 0 2 n 1 1 f x 1 f konstant 0 f balanciert displaystyle begin aligned frac 1 sqrt 2 n langle 0 H n sum x 0 2 n 1 1 f x x rangle amp frac 1 2 n sum x 0 z 0 2 n 1 langle z 1 f x x rangle amp frac 1 2 n sum z 0 2 n 1 1 f x amp begin cases pm 1 amp f text konstant 0 amp f text balanciert end cases end aligned nbsp wobei die Hadamard Transformation nach links angewendet wurde Ist f displaystyle f nbsp balanciert so heben sich in der die positiven und negativen Beitrage weg wohingegen sie sich im konstanten Fall aufsummieren Einzelnachweise Bearbeiten David Deutsch The Church Turing principle and the universal quantum computer In Proceedings of the Royal Society of London A 400 Jahrgang 1985 S 97 doi 10 1098 rspa 1985 0070 royalsocietypublishing org PDF David Deutsch und Richard Jozsa Rapid solutions of problems by quantum computation In Proceedings of the Royal Society of London A 439 Jahrgang 1992 S 553 doi 10 1098 rspa 1992 0167 royalsocietypublishing org PDF R Cleve A Ekert C Macchiavello und M Mosca Quantum algorithms revisited In Proceedings of the Royal Society of London A 454 Jahrgang 1998 S 339 354 doi 10 1098 rspa 1998 0164 arxiv quant ph 9708016 royalsocietypublishing org PDF Lov K Grover A fast quantum mechanical algorithm for database search In Proceedings of the Twenty Eighth Annual ACM Symposium on Theory of Computing 1996 S 212 219 doi 10 1145 237814 237866 arxiv quant ph 9605043 Peter W Shor Polynomial Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer In SIAM J Sci Statist Comput 26 Jahrgang 1997 S 1484 doi 10 1137 S0097539795293172 arxiv quant ph 9508027 siam org PDF Literatur BearbeitenM Homeister Quantum Computing verstehen Springer Vieweg Wiesbaden 2018 funfte Auflage ISBN 978 3 658 22883 5 S 62ff B Lenze Mathematik und Quantum Computing Logos Verlag Berlin 2020 zweite Auflage ISBN 978 3 8325 4716 5 S 51ff R J Lipton K W Regan Quantum Algorithms via Linear Algebra A Primer MIT Press Cambridge MA 2014 ISBN 978 0 262 02839 4 S 77ff M A Nielsen I L Chuang Quantum Computation and Quantum Information Cambridge University Press Cambridge MA 2010 ISBN 978 1 107 00217 3 S 32ff Abgerufen von https de wikipedia org w index php title Deutsch Jozsa Algorithmus amp oldid 235827294