BQP

From Wikipedia, the free encyclopedia

The suspected relationship of BQP to other problem spaces^[1]

In computational complexity theory BQP stands for "Bounded error, Quantum, Polynomial time". It denotes the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

In other words, there is an algorithm for 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).

Similarly to other "bounded error" probabilistic classes the choice of 1/3 in the definition is arbitrary. Changing the constant to any real number $p \,\!$ such that $p \in \left(0,1/2\right)$ does not change the set BQP.

The idea behind this definition is that for any single run of algorithm the probability of error is lower than $p \,\!$ . 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 $p \,\!$ becomes closer to 1/2, but it does not depend on the input size. Probablity of error is exponentially small with regard to the number of repeats.

[edit] Quantum computation

The number of qubits in the computer is allowed to be a polynomial function of the instance size. For example, algorithms are known for factoring an n-bit integer using just over 2n qubits (Shor's algorithm).

Qubits are stored in a quantum register.

Usually, computation on a quantum computer ends with a measurement. This leads to a collapse of the quantum register to one of the basis states. It can be said that the quantum register 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 Shor's algorithm)
Discrete logarithm
Simulation of quantum systems (see universal quantum computer)

[edit] 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 machine plus a source of randomness) is BPP.

BQP contains P and BPP and is contained in PP and PSPACE. 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.

$\mbox{P} \subseteq \mbox{BPP} \subseteq \mbox{BQP}\subseteq \mbox{PP} \subseteq \mbox{PSPACE}$

As the problem of $\mbox{P} \,^{=}_{\neq}\, \mbox{PSPACE}$ 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 class AWPP.

[edit] References

^ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.

Important complexity classes (more)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH