Grover's quantum search algorithm

Quantum algorithms have been devised for a number of tasks.  The most important is probably Shor's algorithm for factorising of large numbers.  Others include Deutsch-Jozsa algorithm for distinguishing certain types of functions and Grover's search algorithm.

The last is perhaps the most easily demonstrated.  It also allows us to show how interference and parallelism, which are essential ingredients in all quantum algorithms, can be used to perform many simultaneous calculations.

The basic idea of the search is to find a particular item in random set of data, called the database.  An example would be trying to find the Ace of Spades in a shuffled pack of cards.  How many cards, on average, would you take from the pack until you found the Ace of Spades?

The answer can be reasoned like this.  Sometimes the Ace of Spades will be near the top of the pack so it will take only a few cards before it is found.  At other times, however, it will be near the bottom of the pack and so it will take almost all of the cards (52) to find it.  On average, it will take the middle value, 52/2 = 26 cards to find it.

The general rule is that for a random database of N items, it will take N/2 tries, on average, to find a particular item.  This how a conventional computer search would work.

Grover's quantum search algorithm, in contrast, takes N tries to find a particular item.  This is a huge saving for large databases.  Searching for one person in the world (population ~6,000,000,000) would take 3,000,000,000 tries using a conventional method, but only 80,000 tries using Grover's quantum algorithm!

Our optical simulator of Grover's algorithm shows how this speed up takes place.  To make things simple, the database contains only 4 items.  The principle idea is that a single photon travels 4 paths simultaneously.  Each path corresponds to an item in the database.  So the photon examines the whole database in one go.  Each photon has a wave associated with it.  The algorithm performs calculations through the interference of the photon's wave.

Interference of waves

We first discuss the interference of waves.  When a pebble is dropped into a pond waves travel outwards on the surface from the disturbance.  Imagine dropping 2 pebbles a small distance apart.  The waves created by each pebble will eventually intersect.  How do the waves behave when they intersect?

The answer is that the wave heights of the two waves simply add.  Two wave crests (high points of the waves) will add to make an even higher wave when they cross, just like adding two positive numbers.  Similarly, two troughs (low points of the waves) will add to make an even deeper trough, just like adding two negative numbers.  These two effects are called constructive interference.  However, when a tough and a crest cross, they cancel each other, just like adding a positive and a negative number can give zero.  This effect is called destructive interference.  

Click on the image to see how waves interfere.

Beam splitter

A beam splitter is a mirror with a very thin reflective coating.  Because the coating is thin, not all the light is reflected and some is transmitted through the mirror.  Typical beam splitters reflect about 50% of the light and transmit the remainder.  Angling a beam splitter at 45o to two light beams allows the two beams to be mixed.  

Click on the image to see a how light waves behave at a beam splitter.

Simulation of a quantum search

When a single photon approaches a beam splitter, the wave splits in two: a reflected part and a transmitted part.  The photon is then in a superposition of two places.  This property is used in the applet below to simulate a quantum search.

Click on the image to see the quantum computer simulation.

The important point is this:  a single photon travels 4 paths simultaneously and examines the entire database in one go.  This is the quantum superposition principle.


The problem with this optical implementation of the search algorithm is that the number of optical paths equals number of elements in database. It would be prohibitive to build a large search engine by this method. This is the scalability problem.  For this reason it is called a simulator of a quantum computer.  See the section Qubit Systems for different approaches that avoid this problem. 

General quantum computers

Despite its limitations, the simulation demonstrates the basic principles on which quantum computers are based: superposition and interference.  The superposition principle allows may operations to occur simultaneously (see quantum parallelism in the Introduction for more details) and the interference is how quantum calculations are performed.  These effects take different forms in different realisations.  For example, in a quantum computer based on atoms, the atoms could be in a superposition of different electronic orbits and the interference could be due to different phases of the electric dipole of the atoms.