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


August 30, 2005


Gil Kalai


Yale University & Hebrew University of Jerusalem


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.


Gil Kalai

Gil Kalai is Professor of Mathematics at the Hebrew University of Jerusalem, He was the recipient of the PĆ³lya Prize in 1992, the Erdos Prize of the Israel Mathematical Society in 1993, and the Fulkerson Prize in 1994. He is known for finding variants of the simplex algorithm that can be proven to run in subexponential time, for showing that every monotone property of graphs has a sharp phase transition and for solving Borsuk’s conjecture on the number of pieces needed to partition convex sets into subsets of smaller diameter and for other fundamental work in combinatorics and convexity.


  • Portrait of Jennifer Chayes

    Jennifer Chayes

    Technical Fellow & Managing Director, Microsoft Research New England, New York City and Montreal