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.

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

, such that 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.

[2] Informally, this is true because polynomial time algorithms are closed under composition.

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

⁠ has not yet been solved, the proof of inequality between BQP and classes mentioned above is supposed to be difficult.

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.

[7] In an extremely informal sense, this can be thought of as giving PH and BQP an identical, but additional, capability and verifying that BQP with the oracle (BQPA) can do things PHA cannot.

The oracle separation gives intuition that BQP may not be contained in PH.

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.

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

APPROX-QCIRCUIT-PROB's completeness makes it useful for proofs showing the relationships between other complexity classes and BQP.

Suppose we have an algorithm A that solves APPROX-QCIRCUIT-PROB, i.e., given a quantum circuit C acting on n qubits, and two numbers

is obtained by measuring several qubits and apply some (classical) logic gates to them.

Since we have exponential power, given a quantum circuit C, we can use classical computer to stimulate each gate in C to get the final state.

time algorithm for calculating the final state, and thus the probability that the first qubit is measured to be one.

Sum of histories is a technique introduced by physicist Richard Feynman for path integral formulation.

The weight on a tree edge from a node in j-th level representing a state

, we sum up the amplitudes of all root-to-leave paths that ends at a node representing

bits are needed to store the histories in addition to some workspace variables.