Polynomial time quantum algorithms, which exploit the non-classical phenomena of superposition and entanglement, have been developed for problems for which no efficient classical algorithm is known. The potential impact of these algorithms on cryptography is devastating: when (and if) scalable quantum computers are built, these algorithms can be used to break most of the public key algorithms in use today. While scalable quantum computers are likely to be decades away, research into post-quantum cryptography (cryptographic algorithms thought to be resistant to quantum computers) has already begun. This course provides an introduction to quantum computation for computer scientists. Familiarity with quantum mechanics (or any physics at all) is not a prerequisite. Instead, relevant aspects of the quantum mechanics formalism will be developed in class. The course begins with an introduction to the QM formalism. It then develops the model of a quantum computer, and discusses how quantum computers enable us to achieve, for some problems, a significant speedup (in some cases an exponential speedup) over any known classical algorithm. This discussion provides the basis for a detailed examination of the most important quantum algorithms, including quantum integer factoring and quantum search. The course concludes with a discussion of quantum key distribution, and a glimpse at what the cryptographic landscape will look like in a world with quantum computers. Required work will include problem sets and a research project.
Some familiarity with linear algebra and with the design and analysis of algorithms.