School of Mathematical Sciences

Department Colloquium

Schreiber 006, 12:15

Hebrew University

Quantum computers are hypothetical devices based on quantum physics that can out-perform

Abstract:

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