The quantum challenge to structural complexity theory

Abstract

A nontechnical survey of recent quantum-mechanical discoveries that challenge generally accepted complexity-theoretic versions of the Church-Turing thesis is presented. In particular, the authors construct an oracle relative to which there exists a set that can be recognized in quantum polynomal time (QP), yet any Turing machine that recognizes it would require exponential time even if allowed to be probabilistic, provided that errors are not tolerated. In particular, QP is not contained in or equal to ZPP relative to this oracle. Furthermore, there are cryptographic tasks that are demonstrably impossible to implement with unlimited computing power probabilistic interactive turning machines, yet they can be implemented even in practice by quantum mechanical apparatus.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>