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:
“You must realize that I was suffering from love and I knew him as intimately as I knew my own image in a mirror. In other words, I knew him only in relation to myself.”
—Angela Carter (1940–1992)
“There is a relation between the hours of our life and the centuries of time. As the air I breathe is drawn from the great repositories of nature, as the light on my book is yielded by a star a hundred millions of miles distant, as the poise of my body depends on the equilibrium of centrifugal and centripetal forces, so the hours should be instructed by the ages and the ages explained by the hours.”
—Ralph Waldo Emerson (1803–1882)
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)
“We commonly say that the rich man can speak the truth, can afford honesty, can afford independence of opinion and action;—and that is the theory of nobility. But it is the rich man in a true sense, that is to say, not the man of large income and large expenditure, but solely the man whose outlay is less than his income and is steadily kept so.”
—Ralph Waldo Emerson (1803–1882)