BQP

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.

Definition

BQP can be viewed as the languages associated with certain bounded-error uniform families of quantum circuits. A language L is in BQP if and only if there exists a polynomial-time uniform family of quantum circuits

{

Q

n

:

n

∈

N

}

{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}

, such that

For all

n

∈

N

{\displaystyle n\in \mathbb {N} }

, Qn takes n qubits as input and outputs 1 bit

For all x in L,

P

r

(

Q

|

x

|

(

x

)

=

1

)

≥

2

3

{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}}

For all x not in L,

P

r

(

Q

|

x

|

(

x

)

=

0

)

≥

2

3

{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}}

Alternatively, one can define BQP in terms of quantum Turing machines. A language L is in BQP if and only if there exists a polynomial quantum Turing machine that accepts L with an error probability of at most 1/3 for all instances.

Similarly to other "bounded error" probabilistic classes, the choice of 1/3 in the definition is arbitrary. 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. The complexity class is unchanged by allowing error as high as 1/2 − n−c on the one hand, or requiring error as small as 2−nc on the other hand, where c is any positive constant, and n is the length of input.

Relationship to other complexity classes

BQP is defined for quantum computers; the corresponding complexity class for classical computers (or more formally for probabilistic Turing machines) is BPP. Just like P and BPP, BQP is low for itself, which means BQPBQP = BQP. Informally, this is true because polynomial time algorithms are closed under composition.