Grover’s algorithm

Let us say a light switch can be either up or down. If we have a 100 light switches for a single bulb, and only one configuration of those switches that turns the light on, how many combinations would you need to try before you can turn the light on?

There are 2100 possible combinations, that is quite a lot! A classical computer works this way when it has to find the unique input to a black-box algorithm (the light switches) that produces a particular output value (the bulb being on). However, there exists a quantum algorithm called Grover’s algorithm, the topic of this video, which can do this task much much faster.

Further thinking

Can you identify the key step in the algorithm?

Can you think of another application of this faster search algorithm?

Solution

Further reading

Link to the original paper by Grover.

Paper by Grover about searching through a database using quantum.