Question of the Week, 31.1.2011
Since the very first idea of a quantum computer, people have found “only” relatively few quantum algorithms on important general problems. If we put aside an efficient simulation of another quantum systems (of central importance for quantum physicists/chemists), “only” two major breakthrough have been made: Shor’s factoring algorithm and Groover’s search algorithm, see e.g. [1].
One of the reasons for the slow discovery of quantum algorithms is the “non-intuitiveness” of quantum mechanics.
On the other hand, there are many people working (searching for new algorithms) in the field of quantum computing nowadays. Also automatically generated quantum algorithms by genetic programming appeared recently, see review [2].
Nevertheless, it is an interesting open question of wide importance, whether someone will find another breakthrough quantum algorithm in future.
References:
[1] Nielsen and Chuang; Quantum Computation and Quantum Information; Cambridge University Press, 2000
[2] A. Gepp and P. Stocks Genet. Program. Evolvable Mach. 10, 181-228 (2009)
Libor Veis