CSE 705: Quantum Computation
This page refers to the Spring 2013 offering of CSE 705 only. The information on this page does not necessarily apply to every offering of CSE 705.
Spring 2013
14185
Quantum computation, theory and practical prospects. Quantum algorithms and exponential speedups. Using arithmetic to simulate quantum circuits, and what this may mean for technological obstacles.
Quantum computing has tantalizing prospects for solving problems believed beyond the reach of today's computers---including breaking codes that would lay bare much of current Internet security. However, technology has been slow to follow, and I moderated a year-long international debate about possible theoretical impediments to building them, beginning with the post http://rjlipton.wordpress.com/2012/01/30/perpetual-motion-of-the-21st-century/ Nevertheless, quantum computing---linear algebra on steroids---has contributed powerful theoretical tools even for non-quantum problems. The seminar will cover the essentials of quantum computing and complexity using a draft mini-book by me and professor Richard J. Lipton, the originator of the above popular blog. The mini-book (to be given out freely) prides itself on being free not only of physics but of special physical notations---it uses only linear algebra. We will cover basic quantum gates, the quantum circuit model, superposition-interference-entanglement, Grover's search algorithm, Shor's period-finding and factoring algorithm, and open questions about the class BQP of problems that reward quantum attacks. My own work has centered on simulating gigantic matrices by smaller polynomials, looking for more than their use in proving that BQP is inside an older class called PP, and finding cases where the circuits can be "de-quantized". This is described at http://rjlipton.wordpress.com/2012/07/08/grilling-quantum-circuits/ Students are expected to participate in discussions and give at least two hours of presentations. Presentations can involve some programming with linear and polynomial algebra. Grading is S/U, 1--3 credits.
CSE596 or equivalent or permission of instructor.
Ph.D.: This course does not fulfill core area or core course requirements.
M.S.: This course does not fulfill core area or core course requirements.
