Is there an model for noise which reduces quantum computation to classical computation?

Опубликовано 9 сентября 2016, 22:15

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.