next up previous contents
Next: Hardware Trends Toward Quantum Up: Motivation Previous: Motivation   Contents

Possible Violation of the Polynomial Church-Turing Thesis

One of the fundamental axioms of computer science is the Church-Turing thesis, which states that any function computable by a ``realistic'' computer can be computed by a Turing machine. An extension of the Church-Turing thesis, the Polynomial Church-Turing thesis states:

...any reasonable attempt to model mathematically computer algorithms and their time performance is bound to end up with a model of computation and associated time cost that is equivalent to Turing machines within a polynomial [15].
This says essentially that all physically realizable computing devices are, within a polynomial factor, equivalent to one another in their time complexity.

In the early 1980's physicist Richard Feynman observed that no classical computer can simulate a quantum mechanical system of particles without incurring exponential slowdown [18]. He also suggested that a computer that behaves in a quantum-mechanical way could potentially simulate such systems without exponential slowdown [18]. The possibility that a quantum computer could violate the polynomial Church-Turning thesis made the study of quantum computation appealing, and provided a strong incentive for studying quantum time complexity. Many of the earliest problems and algorithms for quantum computers were explicitly designed to show tasks that a quantum computer performs exponentially faster than a classical Turing machine.


next up previous contents
Next: Hardware Trends Toward Quantum Up: Motivation Previous: Motivation   Contents
Matthew Hayward Lower Query Bounds in the Quantum Oracle Model GitHub Repository