Wednesday, April 14, 2004
430-438 Soda Hall, Wozniak Lounge
1:00-2:30 p.m.

Senior Researcher in Computer Science

Hebrew University in Jerusalem

From Quantum Computation to Markov Chains and Lattices

Abstract:

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.

Dorit Aharonov is a Senior Researcher in Computer Science at The Hebrew University in Jerusalem. Her thesis, completed in 1998 at Hebrew University with Michael Ben-Or and Avi Wigderson, was on "Noisy Quantum Computations." She has been visiting researcher in the U.S. since 2001, at Cal Tech, MSRI in Berkeley, and in Berkeley / EECS.