13
Looking Ahead

The first generation of quantum algorithms appeared in the 1990s when quantum computers existed only as a concept. On the one hand, the absence of actual quantum hardware was a huge disadvantage since it made direct experiments impossible; on the other hand, it stimulated theoretical research not inhibited by the limitations and constraints of the imperfect early quantum computers. Researchers focused on devising algorithms that would achieve quadratic or even exponential speedup, assuming that powerful, error-free quantum computers would be available one day. It was the time when Shor’s prime factorisation algorithm  [265] and Grover’s search algorithm  [117] were discovered. Incidentally, as the book was about to be released, Peter Shor was named one of the four recipients of the 2022 Breakthrough Prize in Fundamental Physics (along with C. H. Bennett, G. Brassard, and D. Deutsch) for their foundational work in quantum information....