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.