Class Description

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

Linked From

ALL: The Class of All Languages

Literally, the class of ALL languages.

ALL is a gargantuan beast that's been wreaking havoc in the Zoo of late.

First [Aar04b] observed that PP/rpoly (PP with polynomial-size randomized advice) equals ALL, as does PostBQP/qpoly (PostBQP with polynomial-size quantum advice).

Then [Raz05] showed that QIP/qpoly, and even IP(2)/rpoly, equal ALL.

Nor is it hard to show that MA_EXP/rpoly = ALL.

Also, per [Aar18], PDQP/qpoly = ALL.

On the other hand, even though PSPACE contains PP, and EXPSPACE contains MA_EXP, it's easy to see that PSPACE/rpoly = PSPACE/poly and EXPSPACE/rpoly = EXPSPACE/poly are not ALL.

So does ALL have no respect for complexity class inclusions at ALL? (Sorry.)

It is not as contradictory as it first seems. The deterministic base class in all of these examples is modified by computational non-determinism after it is modified by advice. For example, MA_EXP/rpoly means M(A_EXP/rpoly), while (MA_EXP)/rpoly equals MA_EXP/poly by a standard argument. In other words, it's only the verifier, not the prover or post-selector, who receives the randomized or quantum advice. The prover knows a description of the advice state, but not its measured values. Modification by /rpoly does preserve class inclusions when it is applied after other changes.

More about...

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

More about...

PP: Probabilistic Polynomial-Time

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

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

Defined in [Gil77].

PP is closed under union and intersection [BRS91] (this was an open problem for 14 years). More generally, P^PP[log] = PP. Even more generally, PP is closed under polynomial-time truth-table reductions, or even k-round reductions for any constant k [FR96].

Contains P^NP[log] [BHW89] and QMA (see [MW05]). However, there exists an oracle relative to which PP does not contain Δ₂P [Bei94].

PH is in P^PP [Tod89].

BPP [KST+89b] and even BQP [FR98] and YQP* [Yir24] are low for PP: i.e., PP^BQP = PP.
APP is PP-low [Li93].

Equals PostBQP [Aar05b].

For a random oracle A, PP^A is strictly contained in PSPACE^A with probability 1 [ABF+94].

For any fixed k, there exists a language in PP that does not have circuits of size n^k [Vin04b].
Indeed, there exists a language in PP that does not even have quantum circuits of size n^k with quantum advice [Aar06] and [Yir24].

By contrast, there exists an oracle relative to which PP has linear-size circuits [Aar06].

PP can be generalized to the counting hierarchy CH.

More about...

PQP: Probabilistic Quantum Polynomial-Time

The class of decision problems solvable in polynomial time by a quantum Turing machine, with less than 1/2 probability of error.Similar to BQP in definition, but without bounded error.

Defined in [Wat09], where it shown to be equivalent to PP.

Equals PP and therefore PP^BPP [KST+89b] as well as PostBQP [Aar05b].

More about...