computational complexity theoryBQP stands for "Bounded error, Quantum, Polynomial time". It denotes the class of decision problemssolvable by a quantum computerin polynomial time, with an error probability of at most 1/3 for all instances.
In other words, there is an
algorithmfor a quantum computer that solves the decision problem with "high" probability and is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/3 that it will give the wrong answer. (no matter if the correct answer is YES or NO).
The idea behind this definition is that for any single run of algorithm the
probability of erroris lower than . Thus we can run the algorithm a constant number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the Chernoff bound. This number of repeats increases if becomes closer to 1/2, but it does not depend on the inputsize. Probability of error is exponentially small with regard to the number of repeats.
The number of
qubits in the computer is allowed to be a polynomial functionof the instance size.For example, algorithms are known for factoring an "n"-bit integer using just over 2"n" qubits ( Shor's algorithm).
Usually, computation on a quantum computer ends with a measurement. This leads to a collapse of quantum state to one of the basis states. It can be said that the quantum state is measured to be in the correct state with high probability.
Quantum computers have gained widespread interest because some problems of practical interest are known to be in BQP, but suspected to be outside P. Currently, only three such problems are known:
*Integer factorization (see
*Simulation of quantum systems (see
universal quantum computer)
Relationship to other complexity classes
This class is defined for a quantum computer and its natural corresponding class for an ordinary computer (or a
Turing machineplus a source of randomness) is BPP.
BQP contains P and
BPPand is contained in PP and PSPACE. Bernstein and Vazirani, Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997. [http://www.cs.berkeley.edu/~vazirani/bv.ps] ] In fact, BQP is low for PP, meaning that a PP machine achieves no benefit from being able to solve BQP problems instantly, an indication of the possible difference in power between these similar classes. :
As the problem of has not yet been solved, the proof of inequality between BQP and classes mentioned above is supposed to be difficult.
Relation between BQP and NP is not known.
BQP can be shown to be in the
counting complexity classAWPP.
Wikimedia Foundation. 2010.