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) | |||
|---|---|---|---|
| ≥ 2/3 | ≤ 1/3 | ||
| ≤ 1/3 | ≥ 2/3 | ||
| BQP algorithm (k runs) | |||
| > 1 − 2−ck | < 2−ck | ||
| < 2−ck | > 1 − 2−ck | ||
| for some constant c > 0 | |||
BQP can be viewed as the languages associated with certain bounded-error uniform families of quantum circuits.[1] A language L is in BQP if and only if there exists a polynomial-time uniform family of quantum circuits
\{Qn\colonn\inN\}
n\inN
Pr(Q|x|(x)=1)\geq\tfrac{2}{3}
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.[2]
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.[3]
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 .[2] Informally, this is true because polynomial time algorithms are closed under composition. If a polynomial time algorithm calls polynomial time algorithms as subroutines, the resulting algorithm is still polynomial time.
BQP contains P and BPP and is contained in AWPP,[4] PP[5] and PSPACE.[2] 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. The known relationships with classic complexity classes are:
P\subseteqBPP\subseteqBQP\subseteqAWPP\subseteqPP\subseteqPSPACE\subseteqEXP
As the problem of has not yet been solved, the proof of inequality between BQP and classes mentioned above is supposed to be difficult. The relation between BQP and NP is not known. In May 2018, computer scientists Ran Raz of Princeton University and Avishay Tal of Stanford University published a paper[6] which showed that, relative to an oracle, BQP was not contained in PH. It can be proven that there exists an oracle A such that
BQPA\nsubseteqPHA
It has been suspected for many years that Fourier Sampling is a problem that exists within BQP, but not within the polynomial hierarchy. Recent conjectures have provided evidence that a similar problem, Fourier Checking, also exists in the class BQP without being contained in the polynomial hierarchy. This conjecture is especially notable because it suggests that problems existing in BQP could be classified as harder than NP-Complete problems. Paired with the fact that many practical BQP problems are suspected to exist outside of P (it is suspected and not verified because there is no proof that P ≠ NP), this illustrates the potential power of quantum computing in relation to classical computing.[7]
Adding postselection to BQP results in the complexity class PostBQP which is equal to PP.[8] [9]
Promise-BQP is the class of promise problems that can be solved by a uniform family of quantum circuits (i.e., within BQP).[10] Completeness proofs focus on this version of BQP. Similar to the notion of NP-completeness and other complete problems, we can define a complete problem as a problem that is in Promise-BQP and that every other problem in Promise-BQP reduces to it in polynomial time.
The APPROX-QCIRCUIT-PROB problem is complete for efficient quantum computation, and the version presented below is complete for the Promise-BQP complexity class (and not for the total BQP complexity class, for which no complete problems are known). APPROX-QCIRCUIT-PROB's completeness makes it useful for proofs showing the relationships between other complexity classes and BQP.
Given a description of a quantum circuit acting on qubits with gates, where is a polynomial in and each gate acts on one or two qubits, and two numbers
\alpha,\beta\in[0,1],\alpha>\beta
C|0\rangle ⊗
|1\rangle
\geq\alpha
C|0\rangle ⊗
|1\rangle
\leq\beta
Here, there is a promise on the inputs as the problem does not specify the behavior if an instance is not covered by these two cases.
Claim. Any BQP problem reduces to APPROX-QCIRCUIT-PROB.
Proof. Suppose we have an algorithm that solves APPROX-QCIRCUIT-PROB, i.e., given a quantum circuit acting on qubits, and two numbers
\alpha,\beta\in[0,1],\alpha>\beta
\alpha=2/3,\beta=1/3
For any
L\inBQP
\{Qn\colonn\inN\}
n\inN
|x\rangle
n
x\inL,Pr(Qn(|x\rangle)=1)\geq2/3
x\notinL,Pr(Qn(|x\rangle)=0)\geq2/3
|x\rangle
Qn
Cx
| ⊗ n | |
| C | |
| x|0\rangle |
=|x\rangle
|x\rangle
C'=QnCx
C'|0\rangle ⊗ =Qn|x\rangle
Qn
C'|0\rangle ⊗ =Qn|x\rangle
x\inL
A(C)
\alpha=2/3,\beta=1/3
L\inBQP
We begin with an easier containment. To show that
BQP\subseteqEXP
Note that this algorithm also requires
2O(n)
Sum of histories is a technique introduced by physicist Richard Feynman for path integral formulation. APPROX-QCIRCUIT-PROB can be formulated in the sum of histories technique to show that
BQP\subseteqPSPACE
Consider a quantum circuit, which consists of gates,
g1,g2, … ,gm
gj
|0\rangle ⊗
2n
Cn
|x\rangle
j+1
|y\rangle
\langley|gj+1|x\rangle
|y\rangle
gj+1
|x\rangle
|\psi\rangle
|\psi\rangle
More formally, for the quantum circuit, its sum over histories tree is a tree of depth, with one level for each gate
gi
2n
Notice in the sum over histories algorithm to compute some amplitude
\alphax
O(nm)
\alphax
O(nm)
Therefore, in polynomial space, we may compute
\sumx
| 2 | |
| |\alpha | |
| x| |
Notice that compared with the simulation given for the proof that
BQP\subseteqEXP
O(m ⋅ 2mn)
A similar sum-over-histories argument can be used to show that
BQP\subseteqPP
We know
P\subseteqBQP
It is conjectured that BQP solves hard problems outside of P, specifically, problems in NP. The claim is indefinite because we don't know if P=NP, so we don't know if those problems are actually in P. Below are some evidence of the conjecture: