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.
