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.