Ein in hellen Linien gezeichneter Würfel auf dunklem Grund, die Achsen mit erstem, zweitem und drittem Bit beschriftet, jede Ecke in Rot mit ihrer Drei-Bit-Folge von (000) bis (111) beschriftet: die Knoten des 3-Würfels, den der Walk durchsucht.

Algorithmen · Herbst 2019

Quantensuchalgorithmus mit einem Quanten-Random-Walk

Eine Neuimplementierung der Quantenwalk-Suche auf einem Hyperwürfel, numerisch bis zum 5-Würfel gegen die Abschätzung der Publikation geprüft.

Kurz gesagt

Eine klassische Suche in einer unsortierten Liste aus N Einträgen braucht O(N) Abfragen; der Grover-Algorithmus erreicht auf einem Quantencomputer O(√N). Shenvi, Kempe und Whaley erreichen dieselbe Skalierung auf einem anderen Weg, mit einem Quantenwalk auf einem Hyperwürfel. Dieses Projekt in einer Lehrveranstaltung hat ihre Publikation untersucht und den Algorithmus neu implementiert.

Rolle
Allein
Zeitraum
Herbst 2019
Repository
github.com/sadityakr/Quantum-Search-Algorithm
Wolfram MathematicaPythonQuantenwalksNumerische Simulation

Zum Repository →

Studienleistung in der Veranstaltung Quantum Information and Quantum Computation am NISER Bhubaneswar, gelehrt von Dr. Colin Benjamin, zu „A Quantum Random Walk Search Algorithm“ (Shenvi, Kempe & Whaley, Phys. Rev. A 67, 052307, 2003).

Wie

  • Den Schritt auf dem Hyperwürfel in Arithmetik übersetzt. Jeder der 2^n Knoten ist eine n-Bit-Folge, und ein Schritt in Richtung i ist ein XOR mit einem einzelnen gesetzten Bit, das ich als Addition von 2^(i-1) modulo 2^n umgesetzt habe, für den klassischen wie für den Quantenwalk.
  • Zuerst den klassischen Random Walk in Python simuliert, mit der Wahrscheinlichkeit über der Position auf einem 3-Würfel und einem 7-Würfel nach 10 Schritten.
  • Die Suche mit dem Quantenwalk in Wolfram Mathematica gebaut, mit dem Paket Quantum`Notation: der Bitflip-Shift, ein Grover-Münzoperator und ein Orakel, das den Zielzustand |0⟩ invertiert, π/2 × 2^(n/2)-mal iteriert, wie es die Publikation herleitet.
  • Die Simulation über den Punkt hinaus laufen lassen, den die Publikation analysiert, und dort zeigte sich das nichtperiodische Verhalten.

Der Mathematica-Code der Suche auf dunklem Grund. Er lädt das Paket Quantum Notation, setzt n = 3, baut den Shift-Operator als Doppelsumme mit BitXor über die n Richtungen und 2^n Positionen, die gleichmäßige Superposition der Richtungen, die Identitäten für Richtung und Position, die Grover-Münze C0 = -idenc + 2 sc.sc dagger, den Inversionsoperator C2 = C1 - C0, angewendet auf den Zielzustand 0 als in die Münze eingebautes Orakel, den Zeitentwicklungsoperator Evolve = pcoin . shifto, den gleichmäßigen Anfangszustand, t = pi/2 * 2^(n/2) Iterationen und eine Do-Schleife, die Evolve t-mal auf den Zustand anwendet. Die ganze Suche in einer Mathematica-Zelle: Bitflip-Shift, Grover-Münze mit eingebautem Orakel, π/2 × 2^(n/2)-mal iteriert.