Sunday 31 December 2017

Grover's algorithm for the unstructured search problem

After Peter Shor showed how quantum computers can factor numbers efficiently, interest surged in finding other problems which quantum methods solved faster than the best known classical techniques. In 1996 Lov Grover developed such a quantum algorithm for solving the unstructured search problem.

In a generic search problem, we are given a set $S$ of $N$ items. Some of the items in the set are marked. Our task is to find a marked item in the set $S$.

You can think of a search problem like looking up a name in a list. In most cases, the list will be arranged in a way that makes finding names easier. For example, a list of names is often sorted alphabetically. Here we are talking about a list with no discernible ordering. In this case, the best we could do is to check each entry for the desired name.

Monday 28 August 2017

Quantum speed-up in Simon's problem

It has been said that quantum computers will allow us to perform certain computations faster than the regular PCs of today. While this sounds like a remarkable technological advance, it is necessary to clarify what is meant by this:

1. A recipe for solving a computational problem is called an algorithm.  In order to compare the speed of classical and quantum algorithms, we need a way of counting computational steps for classical and quantum algorithms that is fair to compare.

2. How many steps an algorithm needs depends on whether it receives an easy or hard instance of the problem.  Typically we are interested in algorithms that work the best on average. Another issue is that for the algorithms that we do know, we don't usually know if they are the best that we can do (you can sometimes prove a classical algorithm is optimal by using lower-bound arguments). So here  we are really comparing quantum methods with best as-of-yet classical methods. Put differently, it maybe the case (though many believe it unlikely) that classical and quantum computers have the same computational power; we just have not found the best classical algorithms that match the performance of quantum ones.

Here I will describe a problem for which quantum computers have a distinct advantage over classical ones. It is an example of what is called a black-box problem in computer science.