www.wikidata.de-de.nina.az

Quantum Walk Im Bereich der Quanteninformatik ist der auch Quantum Random Walk das Analogon zum klassischen Random Walk

Quantum Walk

Im Bereich der Quanteninformatik ist der Quantum Walk (auch Quantum Random Walk) das Analogon zum klassischen Random Walk. Während beim klassischen Random Walk ein Zustand durch eine Wahrscheinlichkeitsverteilung der möglichen Positionen beschrieben wird, wird er im Quantum Walk als eine Superposition von Positionen beschrieben.

Ähnlich wie beim klassischen Random Walk unterscheidet man zwei Arten von Quantum Walks: den diskreten und den kontinuierlichen.

Motivation Bearbeiten

Quantum Walks sind motiviert durch den weit verbreiteten Einsatz von klassischen Random Walks im Design randomisierter Algorithmen. Sie sind ein Bestandteil mehrerer Quantenalgorithmen. Bei einigen Orakel-Problemen sind Quantum Walks exponentiell schneller als jeder klassische Algorithmus. Für viele praktische Probleme liefern Quantum Walks auch polynomielle Beschleunigungen gegenüber klassischen Algorithmen, zum Beispiel für das Element-Distinctness-Problem (das Problem festzustellen, ob eine Liste Duplikate enthält), dem Problem, zu bestimmen, ob ein Graph dreiecksfrei ist und bei der Evaluierung von NAND-Bäumen. Der wohlbekannte Grover-Algorithmus kann ebenfalls als Quantum Walk betrachtet werden.

Beziehung zum klassischen Random Walk Bearbeiten

Quantum Walks unterscheiden sich in ihrem Verhalten deutlich von klassischen Random Walks. Insbesondere konvergieren sie nicht zu einer Wahrscheinlichkeitsverteilung. Aufgrund des Einflusses von Quanteninterferenz können sie sich signifikant schneller oder langsamer verteilen.

Kontinuierlicher Walk Bearbeiten

Unter bestimmten Umständen können kontinuierliche Quantum Walks ein Modell für universelle Quantenberechnungen liefern. Dies impliziert nicht notwendigerweise Uniformität.

Diskreter Walk Bearbeiten

Wahrscheinlichkeitsverteilungen eindimensionaler diskreter Random Walks nach 50 Zeitschritten. Der Quantum Walk, erzeugt mit der Hadamard-Münze, ist in rot, der klassische Walk in blau eingezeichnet.

Ein diskreter Quantum Walk wird durch eine Münze und einen Verschiebungsoperator spezifiziert, die wiederholt angewendet werden. Das folgende Beispiel soll dies illustrieren. Man stelle sich ein Partikel mit einem Spinfreiheitsgrad eines Spin--Teilchens auf einer Linie (einem eindimensionalem Modell) vor. Sein Zustand kann als Produkt eines Spinzustandes (Eigenzustände der z-Komponente des Spin-Operators mit Eigenwert („Spin hoch“) und („Spin runter“)) und einer Spinposition beschrieben werden. Bei dem Produkt dieser Zustände handelt es sich um das Kronecker-Produkt, welches die beiden Freiheitsgrade separiert. Der Raum der Spinzustände wird Münzraum genannt. Ein bedingter Sprung des Partikels auf der Linie wird durch folgenden Operator beschrieben: . Das Partikel springt bei Spin hoch also nach rechts und bei Spin runter nach links. Wendet man beispielsweise die bedingte Sprungoperation auf einem Initialzustand an, führt das zum Zustand . Rotiert man den Spin zuerst mithilfe einer unitären Transformation in , und wendet dann an, erhält man eine zufällige Bewegung auf der Linie. Als Transformation kann zum Beispiel die Hadamard-Münze gewählt werden: . Wenn der Spin zu diesem Zeitpunkt gemessen wird, erhält man entweder einen Spin hoch an der Stelle 1 oder einen Spin runter an der Stelle -1. Wiederholte Anwendung der Prozedur würde einem klassischen Walk entsprechen, zum Beispiel einem Galtonbrett. Die Idee des Quantum Walk ist allerdings, zwischen den Wiederholungen der Spin-Rotation und des bedingten Springens nicht zu messen (sodass kein Kollaps der Wellenfunktion stattfindet). Auf diese Weise bleibt die Quantenverschränkung erhalten (d. h. die nicht kollabierten Wellenfunktionen) und verschiedene Positionen können miteinander interferieren. Dies führt zu einer drastisch unterschiedlichen Wahrscheinlichkeitsverteilung im Vergleich zum klassischen Walk (Gaußverteilung), wie in der Abbildung rechts deutlich wird. Insbesondere ist erkennbar, dass die Verteilung nicht symmetrisch ist: Obwohl die Hadamard-Münze mit gleicher Wahrscheinlichkeit Spin hoch und Spin runter liefert, tendiert die Verteilung nach rechts, wenn initial ein Spin hoch vorliegt. Dieser Effekt lässt sich grob gesprochen dadurch erklären, dass die Hadamard-Münze mehr destruktive Interferenz für Positionen auf Wegen nach links als nach rechts liefert. Eine symmetrische Verteilung ist möglich mithilfe einer geeigneten Münze oder einem Initialzustand wie , da die Hadamard-Münze keine komplexen Zahlen einführt, sodass Spin hoch und Spin runter sich hier nicht verschränken.

Siehe auch Bearbeiten

Einzelnachweise Bearbeiten

  1. A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by quantum walk, Proc. 35th ACM Symposium on Theory of Computing, pp. 59–68, 2003, quant-ph/0209131.
  2. A. M. Childs, L. J. Schulman, and U. V. Vazirani, Quantum algorithms for hidden nonlinear structures, Proc. 48th IEEE Symposium on Foundations of Computer Science, pp. 395–404, 2007, arxiv:0705.2784.
  3. Andris Ambainis, Quantum walk algorithm for element distinctness, SIAM J. Comput. 37 (2007), no. 1, 210–239, arxiv:quant-ph/0311001, preliminary version in FOCS 2004.
  4. F. Magniez, M. Santha, and M. Szegedy, Quantum algorithms for the triangle problem, Proc. 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1109–1117, 2005, arxiv:quant-ph/0310134.
  5. Andrew M. Childs: Universal Computation by Quantum Walk. arxiv:0806.1972
  6. Julia Kempe: Quantum random walks - an introductory overview. In: Contemporary Physics. 44. Jahrgang, Nr. 4, 1. Juli 2003, ISSN 0010-7514, S. 307–327, doi:10.1080/00107151031000110776, arxiv:quant-ph/0303081.

Literatur Bearbeiten

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:
Im Bereich der Quanteninformatik ist der Quantum Walk auch Quantum Random Walk das Analogon zum klassischen Random Walk Wahrend beim klassischen Random Walk ein Zustand durch eine Wahrscheinlichkeitsverteilung der moglichen Positionen beschrieben wird wird er im Quantum Walk als eine Superposition von Positionen beschrieben Ahnlich wie beim klassischen Random Walk unterscheidet man zwei Arten von Quantum Walks den diskreten und den kontinuierlichen Inhaltsverzeichnis 1 Motivation 2 Beziehung zum klassischen Random Walk 3 Kontinuierlicher Walk 4 Diskreter Walk 5 Siehe auch 6 Einzelnachweise 7 Literatur 8 WeblinksMotivation BearbeitenQuantum Walks sind motiviert durch den weit verbreiteten Einsatz von klassischen Random Walks im Design randomisierter Algorithmen Sie sind ein Bestandteil mehrerer Quantenalgorithmen Bei einigen Orakel Problemen sind Quantum Walks exponentiell schneller als jeder klassische Algorithmus 1 2 Fur viele praktische Probleme liefern Quantum Walks auch polynomielle Beschleunigungen gegenuber klassischen Algorithmen zum Beispiel fur das Element Distinctness Problem das Problem festzustellen ob eine Liste Duplikate enthalt 3 dem Problem zu bestimmen ob ein Graph dreiecksfrei ist 4 und bei der Evaluierung von NAND Baumen Der wohlbekannte Grover Algorithmus kann ebenfalls als Quantum Walk betrachtet werden Beziehung zum klassischen Random Walk BearbeitenQuantum Walks unterscheiden sich in ihrem Verhalten deutlich von klassischen Random Walks Insbesondere konvergieren sie nicht zu einer Wahrscheinlichkeitsverteilung Aufgrund des Einflusses von Quanteninterferenz konnen sie sich signifikant schneller oder langsamer verteilen Kontinuierlicher Walk BearbeitenUnter bestimmten Umstanden konnen kontinuierliche Quantum Walks ein Modell fur universelle Quantenberechnungen liefern Dies impliziert nicht notwendigerweise Uniformitat 5 Diskreter Walk Bearbeiten nbsp Wahrscheinlichkeitsverteilungen eindimensionaler diskreter Random Walks nach 50 Zeitschritten Der Quantum Walk erzeugt mit der Hadamard Munze ist in rot der klassische Walk in blau eingezeichnet Ein diskreter Quantum Walk wird durch eine Munze und einen Verschiebungsoperator spezifiziert die wiederholt angewendet werden Das folgende Beispiel soll dies illustrieren 6 Man stelle sich ein Partikel mit einem Spinfreiheitsgrad eines Spin 1 2 displaystyle frac 1 2 nbsp Teilchens auf einer Linie einem eindimensionalem Modell vor Sein Zustand kann als Produkt eines Spinzustandes s H C displaystyle s rangle in mathcal H C left mathord uparrow right rangle left mathord downarrow right rangle nbsp Eigenzustande der z Komponente des Spin Operators mit Eigenwert 1 2 displaystyle frac 1 2 nbsp Spin hoch und 1 2 displaystyle frac 1 2 nbsp Spin runter und einer Spinposition i H P n n Z displaystyle i rangle in mathcal H P n rangle n in mathbb Z nbsp beschrieben werden Bei dem Produkt dieser Zustande handelt es sich um das Kronecker Produkt welches die beiden Freiheitsgrade separiert Der Raum der Spinzustande wird Munzraum genannt Ein bedingter Sprung des Partikels auf der Linie wird durch folgenden Operator beschrieben S i i 1 i i i 1 i displaystyle S left mathord uparrow right rangle left langle mathord uparrow right otimes sum limits i i 1 rangle langle i left mathord downarrow right rangle left langle mathord downarrow right otimes sum limits i i 1 rangle langle i nbsp Das Partikel springt bei Spin hoch also nach rechts und bei Spin runter nach links Wendet man beispielsweise die bedingte Sprungoperation auf einem Initialzustand 0 displaystyle left mathord uparrow right rangle otimes 0 rangle nbsp an fuhrt das zum Zustand 1 displaystyle left mathord uparrow right rangle otimes 1 rangle nbsp Rotiert man den Spin zuerst mithilfe einer unitaren Transformation C displaystyle C nbsp in H C displaystyle mathcal H C nbsp und wendet dann S displaystyle S nbsp an erhalt man eine zufallige Bewegung auf der Linie Als Transformation kann zum Beispiel die Hadamard Munze gewahlt werden 0 H 1 2 0 S 1 2 1 1 displaystyle left mathord uparrow right rangle otimes 0 rangle overset H longrightarrow frac 1 sqrt 2 left mathord uparrow right rangle left mathord downarrow right rangle otimes 0 rangle overset S longrightarrow frac 1 sqrt 2 left mathord uparrow right rangle otimes 1 rangle left mathord downarrow right rangle otimes 1 rangle nbsp Wenn der Spin zu diesem Zeitpunkt gemessen wird erhalt man entweder einen Spin hoch an der Stelle 1 oder einen Spin runter an der Stelle 1 Wiederholte Anwendung der Prozedur wurde einem klassischen Walk entsprechen zum Beispiel einem Galtonbrett Die Idee des Quantum Walk ist allerdings zwischen den Wiederholungen der Spin Rotation und des bedingten Springens nicht zu messen sodass kein Kollaps der Wellenfunktion stattfindet Auf diese Weise bleibt die Quantenverschrankung erhalten d h die nicht kollabierten Wellenfunktionen und verschiedene Positionen konnen miteinander interferieren Dies fuhrt zu einer drastisch unterschiedlichen Wahrscheinlichkeitsverteilung im Vergleich zum klassischen Walk Gaussverteilung wie in der Abbildung rechts deutlich wird Insbesondere ist erkennbar dass die Verteilung nicht symmetrisch ist Obwohl die Hadamard Munze mit gleicher Wahrscheinlichkeit Spin hoch und Spin runter liefert tendiert die Verteilung nach rechts wenn initial ein Spin hoch vorliegt Dieser Effekt lasst sich grob gesprochen dadurch erklaren dass die Hadamard Munze mehr destruktive Interferenz fur Positionen auf Wegen nach links als nach rechts liefert Eine symmetrische Verteilung ist moglich mithilfe einer geeigneten Munze oder einem Initialzustand wie 1 2 i 0 displaystyle frac 1 sqrt 2 left mathord uparrow right rangle mathrm i left mathord downarrow right rangle otimes 0 rangle nbsp da die Hadamard Munze keine komplexen Zahlen einfuhrt sodass Spin hoch und Spin runter sich hier nicht verschranken Siehe auch BearbeitenPfadintegralEinzelnachweise Bearbeiten A M Childs R Cleve E Deotto E Farhi S Gutmann and D A Spielman Exponential algorithmic speedup by quantum walk Proc 35th ACM Symposium on Theory of Computing pp 59 68 2003 quant ph 0209131 A M Childs L J Schulman and U V Vazirani Quantum algorithms for hidden nonlinear structures Proc 48th IEEE Symposium on Foundations of Computer Science pp 395 404 2007 arxiv 0705 2784 Andris Ambainis Quantum walk algorithm for element distinctness SIAM J Comput 37 2007 no 1 210 239 arxiv quant ph 0311001 preliminary version in FOCS 2004 F Magniez M Santha and M Szegedy Quantum algorithms for the triangle problem Proc 16th ACM SIAM Symposium on Discrete Algorithms pp 1109 1117 2005 arxiv quant ph 0310134 Andrew M Childs Universal Computation by Quantum Walk arxiv 0806 1972 Julia Kempe Quantum random walks an introductory overview In Contemporary Physics 44 Jahrgang Nr 4 1 Juli 2003 ISSN 0010 7514 S 307 327 doi 10 1080 00107151031000110776 arxiv quant ph 0303081 Literatur BearbeitenJulia Kempe Quantum random walks an introductory overview In Contemporary Physics 44 Jahrgang Nr 4 2003 S 307 327 doi 10 1080 00107151031000110776 arxiv quant ph 0303081 bibcode 2003ConPh 44 307K Andris Ambainis Quantum walks and their algorithmic applications In International Journal of Quantum Information 1 Jahrgang Nr 4 2003 S 507 518 doi 10 1142 S0219749903000383 arxiv quant ph 0403120 Miklos Santha Quantum walk based search algorithms In Th Theory and Applications of Models of Computation TAMC Xian LNCS 4978 5 Jahrgang Nr 8 April 2008 S 31 46 arxiv 0808 0059 bibcode 2008arXiv0808 0059S Salvador E Venegas Andraca Quantum walks a comprehensive review In Quantum Information Processing 11 Jahrgang Nr 5 2012 S 1015 1106 doi 10 1007 s11128 012 0432 5 arxiv 1201 4780v2 Salvador E Venegas Andraca Quantum Walks for Computer Scientists Abgerufen am 16 Oktober 2008 Weblinks BearbeitenInternational Workshop on Mathematical and Physical Foundations of Discrete Time Quantum Walk Quantum walk Abgerufen von https de wikipedia org w index php title Quantum Walk amp oldid 217466296