Simulated Quantum Computer Algorithm for Database Searching

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

This is a simulation of Grover's algorithm for searching a database for a single target address (secretly selected to be the qubit at n=7—pretend you don't know this!). Successive applications of quantum-computer operations called inversion and diffusion increase the amplitude of the target qubit. Reading the quantum register causes collapse of its wavefunction. The probability of each possible answer is then equal to the square of its amplitude. For a database of dimension N, the probability of locating the target is maximized after approximately π/4 iterations. Compare this with the 50% probability for success in a classical search after N/2 steps. Paradoxically, the quantum algorithm becomes worse with additional iterations (actually, the probability oscillates).

Contributed by: S. M. Blinder (March 2011)
After work by: Tad Hogg
Open content licensed under CC BY-NC-SA


Snapshots


Details

L. Grover, "Quantum Mechanics Helps in Searching for a Needle in a Haystack," Physical Review Letters, 79(2), 1997 pp. 325–328.

S. M. Blinder, Introduction to Quantum Mechanics in Chemistry, Materials Science, and Biology, Burlington, MA: Elsevier Academic Press, 2004 pp. 283–284.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send