Is there an (interesting?/realistic?/universal?) model for low-rate noise which reduces quantum computation to classical computation?

Gil Kalai

Yale and Hebrew University

Monday, October 17 at 2:30 in AKW 200

ABSTRACT 

Quantum computation is a remarkable model of computation initiated by
Deutsch and others in the mid 1980s. Shor's famous result (in 1994)  gave
a polynomial quantum algorithm for factoring, and along with results by
Simon, Grover and others indicates that quantum computers may well be much
more powerful than ordinary computers. Quantum error-correction and the
remarkable "threshold theorem" (achieved by several groups of researchers
in the mid 1990's) show that the full power of quantum computation is
preserved for noisy quantum computers when the noise rate is small and the
noise satisfies certain natural "locality" conditions.

Studying models of noise under which the power of quantum computers
reduces to the power of classical computers is an interesting
complexity-theoretic/mathematical problem.  We will (informally)  discuss
potential examples for such models where the noise rate is still small and
the "locality" condition is (in some sense) approximately satisfied.

	    



Return to DMTCS home page.