Complexity and algorithms in quantum computation

In 1982 Feynman noted that the simulation of a quantum process on a classical computer appears to generally involve an exponential slowdown in running time compared to the evolution of the process itself. More recently in quantum computation this effect has been turned around and exploited for computational advantage by formulating quantum processes (quantum algorithms) whose evolution corresponds to the performance of useful computational tasks. Thus the quantum algorithm will engender an exponential speedup in computing time. The most famous such quantum algorithm is Shor´s algorithm for factorising whole numbers. It factorises a number having d digits in a time of order less than d whereas no known classical algorithm can perform factorisation in a time bounded by any polynomial in d. In theoretical computer science, computational complexity is generally characterised by classifying computational tasks into complexity classes such as P, BPP and NP. It therefore appears that quantum computers will be able to transgress some of the boundaries set by these classes