BQP

from Wikipedia, the free encyclopedia
The position of BQP relative to other problem classes

The complexity class BQP (from English bounded-error quantum polynomial time ) is a term from complexity theory , a branch of theoretical computer science . BQP includes all problems that can be solved on a quantum computer in polynomial time with an error probability of no more than 1/3. It is the equivalent of the class BPP , which is defined for the time required on Turing machines . As with the BPP class, the BQP definition of the error probability to 1/3 is arbitrary. By applying a BQP algorithm several times , an arbitrarily low error probability can be achieved.

BQP was introduced in 1993 by Umesh Vazirani and Ethan Bernstein .

Relationship to other complexity classes

The complexity classes P and BPP are contained in BQP, BQP is contained in PP and thus also in PSPACE . It is unknown whether these inclusions are real or not.

Problems in BQP

There are several known issues in BQP that are not believed to be in BPP. The best known is the factoring problem , which can be solved with Shor's algorithm .

Individual evidence

  1. ↑ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information . Cambridge: Cambridge University Press. ISBN 0-521-63503-9 .
  2. ^ Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: Quantum Computability . In: SIAM Journal on Computing . tape 26 , no. 5 . SIAM , 1997, p. 1524-1540 ( psu.edu [PDF]).

literature

  • L. Adleman , J. Demarrais, MA Huang. Quantum computability . SIAM J. Comp., 26 (5): 1524-1540, 1997.
  • E. Bernstein, U. Vazirani. Quantum complexity theory . SIAM J. Comp., 26 (5): 1411-1473, 1997.

Web links

  • BQP . In: Complexity Zoo. (English)