By the early nineties it was known that a quantum computer could be more efficient than any classical computer for certain tasks of the Complexity-Theoretic Church-Turing thesis holds . Nonetheless investigations into these areas were largely driven by academic curiosity. There was not much economic motive for people to spend lots of money or time trying to build a quantum computer.

That changed in 1994 when Peter Shor, a scientist working for Bell Labs, devised a polynomial time algorithm for factoring large numbers on a quantum computer. This discovery drew great attention to the field of quantum computing.