Quantum Computing

Intermediate—Fall

Physicists and philosophers have been trying to understand the strangeness of the subatomic world as revealed by quantum theory since its inception back in the 1920s; but it wasn't until the 1980s—more than a half-century after the development of the theory—that computer scientists first began to suspect that quantum physics might hold profound implications for computing, as well, and that its inherent weirdness might possibly be transformed into a source of immense computational power. This dawning realization was followed soon afterward by key theoretical and practical advances, including the discovery of several important algorithms for quantum computers that could potentially revolutionize (and disrupt) the cryptographic systems protecting practically all of our society’s electronic banking, commerce, telecommunications, and national security systems. Around the same time, researchers succeeded in building the first working quantum computers, albeit on a very small scale. Today, the multidisciplinary field of quantum computing lies at the intersection of computer science, mathematics, physics, and engineering and is one of the most active and fascinating areas in science—with potentially far-reaching consequences for the future. This course will introduce students to the theory and applications of quantum computing from the perspective of computer science. Topics to be covered will include bits and qubits, quantum logic gates and reversible computing, Deutsch’s algorithm, Grover's search algorithm, Shor’s factoring algorithm, and applications to cryptography. No advanced background in physics, mathematics, or computer programming is necessary beyond a basic familiarity with linear algebra. We will study the quantitative, mathematical theory of quantum computing in detail but will also consider broader philosophical questions about the nature of physical reality, as well as the future of computing technologies. Prerequisite: one semester of linear algebra or equivalent mathematical preparation.