Quantum Computation - 605.728

Quantum computing is no longer a purely theoretical notion. The NSA and NIST are preparing to transition to quantum resistant cryptography. We have now entered the intermediate-scale quantum era, with near-term applications such as quantum machine learning being explored. Scalable quantum computers aren’t here yet, but ongoing developments suggest they are on their way. 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 algorithms 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. Prerequisites: Some familiarity with linear algebra and with the design and analysis of algorithms or instructor permission.