Scalable quantum computers aren’t here yet. But recent progress suggests they may be on their way, and that it is now time to start planning for their potential impact: NSA announced in 2015 a shift in focus from elliptic curve to quantum resistant cryptography, and NIST has initiated a large-scale study of post-quantum cryptography. This course provides an introduction to quantum computation for computer scientists: the focus is on algorithms rather than physical devices, and familiarity with quantum mechanics (or any physics at all) is not a prerequisite. Instead, pertinent aspects of the quantum mechanics formalism are developed as needed in class. The course begins with an introduction to the QM formalism. It then develops the abstract 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 quantum integer factoring, quantum search, and other quantum algorithms. The course also explores quantum error correction, quantum teleportation, and quantum cryptography. It concludes with a glimpse at what the cryptographic landscape will look like in a world with quantum computers. Required work includes problem sets and a research project.
Some familiarity with linear algebra and with the design and analysis of algorithms.