Relation To Computational Complexity Theory
The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time". Quantum computers only run probabilistic algorithms, so BQP on quantum computers is the counterpart of BPP ("bounded error, probabilistic, polynomial time") on classical computers. It is defined as the set of problems solvable with a polynomial-time algorithm, whose probability of error is bounded away from one half. A quantum computer is said to "solve" a problem if, for every instance, its answer will be right with high probability. If that solution runs in polynomial time, then that problem is in BQP.
BQP is contained in the complexity class #P (or more precisely in the associated class of decision problems P#P), which is a subclass of PSPACE.
BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.
The capacity of a quantum computer to accelerate classical algorithms has rigid limits — upper bounds of quantum computation's complexity. The overwhelming part of classical calculations cannot be accelerated on a quantum computer. A similar fact takes place for particular computational tasks, like the search problem, for which Grover's algorithm is optimal.
Although quantum computers may be faster than classical computers, those described above can't solve any problems that classical computers can't solve, given enough time and memory (however, those amounts might be practically infeasible). A Turing machine can simulate these quantum computers, so such a quantum computer could never solve an undecidable problem like the halting problem. The existence of "standard" quantum computers does not disprove the Church–Turing thesis. It has been speculated that theories of quantum gravity, such as M-theory or loop quantum gravity, may allow even faster computers to be built. Currently, defining computation in such theories is an open problem due to the problem of time, i.e. there currently exists no obvious way to describe what it means for an observer to submit input to a computer and later receive output.
Read more about this topic: Quantum Computer
Famous quotes containing the words relation to, relation, complexity and/or theory:
“Unaware of the absurdity of it, we introduce our own petty household rules into the economy of the universe for which the life of generations, peoples, of entire planets, has no importance in relation to the general development.”
—Alexander Herzen (1812–1870)
“Art should exhilarate, and throw down the walls of circumstance on every side, awakening in the beholder the same sense of universal relation and power which the work evinced in the artist, and its highest effect is to make new artists.”
—Ralph Waldo Emerson (1803–1882)
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)
“Thus the theory of description matters most.
It is the theory of the word for those
For whom the word is the making of the world,
The buzzing world and lisping firmament.”
—Wallace Stevens (1879–1955)