## Simulator

## Contents

- Introduction
- Simulator
- Qubit Systems
- More Information
38846 visits

### 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

*, which are essential ingredients in all quantum algorithms, can be used to perform many simultaneous calculations.*

**parallelism**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

**. 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**

*simultaneously***of the photon's wave.**

*interference*### 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 45^{o} 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

**of two places. This property is used in the applet below to simulate a quantum search.**

*superposition*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.

### Limitations

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

**for different approaches that avoid this problem.**

*Qubit Systems*### General quantum computers

Despite its limitations, the simulation demonstrates the basic principles on which quantum computers are based:
** superposition** and

**. The superposition principle allows may operations to occur simultaneously (see**

*interference***in the**

*quantum parallelism***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.**

*Introduction*