BQP

This article is about the computational complexity class. For other uses, see BQP (disambiguation).
Diagram of randomised complexity classes
BQP in relation to other probabilistic complexity classes (ZPP, RP, co-RP, BPP, PP), which generalise P within PSPACE. It is unknown if any of these containments are strict.

In computational complexity theory, bounded-error quantum polynomial time (BQP) is 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.[1] It is the quantum analogue to the complexity class BPP.

A decision problem is a member of BQP if there exists a quantum algorithm (an algorithm that runs on a quantum computer) that solves the decision problem with high probability and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3.

BQP algorithm (1 run)
Answer
produced
Correct
answer
 Yes No
Yes ≥ 2/3 ≤ 1/3
No ≤ 1/3 ≥ 2/3
BQP algorithm (k runs)
Answer
produced
Correct
answer
 Yes No
Yes > 1 − 2−ck < 2−ck
No < 2−ck > 1 − 2−ck
for some constant c > 0
  1. ^ Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.