Quantum Algorithms

Quantum computers turn out to be technically hard to build, and error rates remain a fundamental concern for quantum computers while classical computers can, in principle, perform the aforementioned calculations anyway. Why should quantum computation be attractive?

Peter Shor’s quantum factorization algorithm (Shor, 1994, 1997) brought great attention to quantum computation, even from the public, at the turn of the millennium. The factorization of large numbers was the first practically important task that is not feasible on a classical computer but can be performed efficiently on a quantum computer.

This collection of tutorial documents explores several elementary examples of quantum algorithms that efficiently solve problems known to be exponentially hard with classical algorithms. Although some of them may be of little use for practical applications, these examples are still interesting to elucidate the ideas and features behind quantum algorithms that distinguish them from classical algorithms.

Quantum teleportation is included here. Precisely speaking, it is a quantum communication protocol, rather than a quantum algorithm. Nonetheless, we include it here because it is a simple yet fascinating example demonstrating what one can do with quantum states that is not possible at all with classical information. Quantum teleportation makes key parts of many quantum algorithms as well.

See also Chapter 4 of the