Class Description

BPP_path: Threshold BPP

Same as BPP, except that now the computation paths need not all have the same length.

Defined in [HHT97], where the following was also shown:

• BPP_path contains MA and P^NP[log], and is contained in PP and BPP^NP.
• BPP_path is closed under complementation, intersection, and union.
• If BPP_path = BPP_path^BPP_path, then PH collapses to BPP_path.
• If BPP_path contains Σ₂P, then PH collapses to BPP^NP.

There exists an oracle relative to which BPP_path is not contained in Σ₂P [BGM02].

An alternate characterization of BPP_path uses the idea of post-selection. That is, BPP_path is the class of languages ${\displaystyle L}$ for which there exists a pair of polynomial-time Turing machines ${\displaystyle A}$ and ${\displaystyle B}$ such that the following conditions hold for all ${\displaystyle x}$:

• If ${\displaystyle x\in L}$, ${\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (\left\vert x\right\vert )}}\left[A(x,r)\mid B(x,r)\right]\geq {\frac {2}{3}}}$.
• If ${\displaystyle x\notin L}$, ${\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (\left\vert x\right\vert )}}\left[A(x,r)\mid B(x,r)\right]<{\frac {1}{3}}}$.
• ${\displaystyle \Pr _{r\in \{0,1\}^{\mathrm {poly} (n)}}\left[B(x,r)\right]>0}$.

We say that ${\displaystyle B}$ is the post-selector. Intuitively, this characterization allows a BPP machine to require that its random bits have some special but easily verifiable property. This characterization makes the inclusion NP ⊆ BPP_path nearly trivial.

See Also: PostBQP (quantum analogue).

Linked From

BPP: Bounded-Error Probabilistic Polynomial-Time

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes' then at least 2/3 of the computation paths accept.
2. If the answer is 'no' then at most 1/3 of the computation paths accept.

(Here all computation paths have the same length.)

Often identified as the class of feasible problems for a computer with access to a genuine random-number source.

Defined in [Gil77].

Contained in Σ₂P ∩ Π₂P [Lau83], and indeed in ZPP^NP [GZ97].

If BPP contains NP, then RP = NP [Ko82,Gil77] and PH is contained in BPP [Zac88].

If any problem in E requires circuits of size 2^Ω(n), then BPP = P [IW97] (in other words, BPP can be derandomized).

Contained in O₂P since problems requiring exponential sized circuits can be verified in O₂E [GLV24] [Li23] which can be used to derandomize [IW97].

Indeed, any proof that BPP = P requires showing either that NEXP is not in P/poly, or else that #P requires superpolynomial-size arithmetic circuits [KI02].

BPP is not known to contain complete languages. [Sip82], [HH86] give oracles relative to which BPP has no complete languages.

There exist oracles relative to which P = RP but still P is not equal to BPP [BF99].

In contrast to the case of P, it is unknown whether BPP collapses to BPTIME(n^c) for some fixed constant c. However, [Bar02] and [FS04] have shown hierarchy theorems for BPP with a small amount of advice.

A zero-one law exists stating that BPP has p-measure zero unless BPP = EXP [Mel00].

Equals Almost-P.

See also: BPP_path.

More about...

BQP: Bounded-Error Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.

One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).

BQP is often identified as the class of feasible problems for quantum computers.

Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.

Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.

BQP^BQP = BQP [BV97].

[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.

There exist oracles relative to which:

• BQP does not equal to BPP [BV97] (and by similar arguments, is not in P/poly).
• BQP is not contained in MA [Wat00].
• BQP is not contained in PH [RT18] (see also [Wu18]).
• BQP is not contained in Mod_pP for prime p [GV02].
• NP, and indeed NP ∩ coNP, are not contained in BQP with probability 1 relative to a random oracle and a random permutation oracle, respectively [BBB+97].
• SZK is not contained in BQP [Aar02].
• BQP is not contained in SZK (follows easily using the quantum walk problem in [CCD+03]).
• BQP is not contained in BPP_path [Aar10] (see also [Che16]).
• PPAD is not contained in BQP [Li11].
• P=BQP and PH is infinite [FR98].

If P=BQP relative to a random oracle then BQP=BPP [FR98].

More about...

PostBPP: BPP With Postselection

Alias for BPP_path.

More about...

PostBQP: BQP With Postselection

A class inspired by the proverb, "if at first you don't succeed, try, try again."

Formally, the class of decision problems solvable by a BQP machine such that

• If the answer is 'yes' then the second qubit has at least 2/3 probability of being measured 1, conditioned on the first qubit having been measured 1.
• If the answer is 'no' then the second qubit has at most 1/3 probability of being measured 1, conditioned on the first qubit having been measured 1.
• On any input, the first qubit has a nonzero probability of being measured 1.

Defined in [Aar05b], where it is also shown that PostBQP equals PP.

[Aar05b] also gives the following alternate characterizations of PostBQP (and therefore of PP):

• The quantum analogue of BPP_path.
• The class of problems solvable in quantum polynomial time if we allow arbitrary linear operations (not just unitary ones). Before measuring, we divide all amplitudes by a normalizing factor to make the probabilities sum to 1.
• The class of problems solvable in quantum polynomial time if we take the probability of measuring a basis state with amplitude α to be not |α|² but |α|^p, where p is an even integer greater than 2. (Again we need to divide all amplitudes by a normalizing factor to make the probabilities sum to 1.)

More about...

SBP: Small Bounded-Error Probability

The class of decision problems for which the following holds. There exists a #P function f and an FP function g such that, for all inputs x,

1. If the answer is "yes" then f(x) > g(x).
2. If the answer is "no" then f(x) < g(x)/2.

Defined in [BGM02], where the following was also shown:

• SBP contains MA, WAPP, and ∃BPP.
• SBP is contained in AM and BPP_path.
• There exists an oracle relative to which SBP is not contained in Σ₂P.
• SBP is closed under union.

There exists an oracle relative to which SBP is not closed under intersection [GLM+15].

If SAT can be solved by an NP-machine with sub-exponential number of accepting paths, then SBP = AM [Vol20].

More about...