Simulated Quantum Computer Algorithm for Database Searching
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
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.
Permanent Citation