Computer Science Colloquium, 2004-2005

Dorit Aharonov, School of Computer Science and Engineering, Hebrew University of Jerusalem

From Quantum Computation to Markov Chains and Lattices

The fascinating field of quantum computation now faces major challenges which are intimately related to other areas in theoretical computer science: coding theory, Markov chains, lattices, and more. Starting with a (gentle) introduction to quantum computation, I will proceed to make these connections more explicit, while walking you through two of the most important issues in the field. The first is making quantum computers more resilient to noise, which is arguably the main bottleneck towards large scale realization of quantum computers; The second is breaking past our current barrier of designing new quantum algorithms. Our recent results in the latter area have led in a surprising way to a solution of an open question regarding the (totally classical) complexity of lattice problems. If time permits, I will tell you the story behind this unexpected connection.

Shuly Wintner
Last modified: Tue Feb 15 07:49:25 IST 2005