BQP

This article is about the computational complexity class. For other uses, see BQP (disambiguation).

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. 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