Topics
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.
Description
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 this post on the field-wide weblog I co-manage, Gödel's Lost Letter and P=NP.
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 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 here.
Organization
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.
Prerequisites: CSE596 or equivalent or permission of instructor.
Meeting times TBA.