Tel-Aviv University
School of Mathematical Sciences

Department Colloquium

Monday, November 19, 2012

Schreiber 006, 12:15

Gil Kalai

Hebrew University

Quantum information, computation, and noise

Quantum computers are hypothetical devices based on quantum physics that can out-perform
classical computers. A famous algorithm by Peter Shor shows that quantum computers can factor an
interger n in C(log n)^3 steps. The feasibility of computationally-superior quantum computers  is one of
the most fascinating and clear-cut scientific problems of our time. The main concern is that quantum
systems are inherently noisy. Roughly what this means for quantum computers is that the internal states
of quantum registers may vary unpredictably outside the range that allows the quantum algorithm to continue.
To overcome this difficulty a fascinating notion of quantum error-correction and a remarkable theory of
quantum fault-tolerance were developed.

The question if quantum computers are feasible offers us mathematicians interesting mathematical
questions, and specifically, how to mathematically model noisy quantum evolutions and to express the
insight that quantum systems are "inherently noisy." In the lecture I will describe my work on this topic
and some highlights in a recent discussion between Aram Harrow and me on the possibility within quantum
mechanics that universal (or just superior)  quantum computers are impossible.

The talk will be self contained: no prior knowledge about quantum computers will be assumed.

Coffee will be served at 12:00 before the lecture
at Schreiber building 006