PostBQP

In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error (in the sense that the algorithm is correct at least 2/3 of the time on all inputs). Postselection is not considered to be a feature that a realistic computer (even a quantum one) would possess, but nevertheless postselecting machines are interesting from a theoretical perspective. Removing either one of the two main features (quantumness, postselection) from PostBQP gives the following two complexity classes, both of which are subsets of PostBQP:
BQP is the same as PostBQP except without postselection
BPPpath is the same as PostBQP except that instead of quantum, the algorithm is a classical randomized algorithm (with postselection)

The addition of postselection seems to make quantum Turing machines much more powerful: Scott Aaronson proved PostBQP is equal to PP, a class which is believed to be relatively powerful, whereas BQP is not known even to contain the seemingly smaller class NP. Using similar techniques, Aaronson also proved that small changes to the laws of quantum computing would have significant effects. As specific examples, under either of the two following changes, the "new" version of BQP would equal PP:
if we broadened the definition of 'quantum gate' to include not just unitary operations but linear operations, or
if the probability of measuring a basis state was proportional to instead of for any even integer p > 2.

Scott Aaronson showed that the complexity classes \mathsf{PostBQP} (postselected bounded error quantum polynomial time) and PP (probabilistic polynomial time) are equal. The result was significant because this quantum computation reformulation of \mathsf{PP} gave new insight and simpler proofs of properties of \mathsf{PP}
The usual definition of a \mathsf{PostBQP} circuit family is one with two outbit qubits P (postselection) and Q (output) with a single measurement of P and Q at the end such that the probability of measuring 1=P = 1 has nonzero probability, the conditional probability Pr[Q = 1|P = 1] ≥ 2/3 if the input x is in the language, and Pr[Q = 0|P = 1] ≥ 2/3 if the input x is not in the language. For technical reasons we tweak the definition of \mathsf{PostBQP} as follows: we require that 1=Pr[P = 1] ≥ 2^(−n^(c)) for some constant c depending on the circuit family. Note this choice does not affect the basic properties of \mathsf{PostBQP} , and also it can be shown that any computation consisting of typical gates (e. g. Hadamard, Toffoli) has this property whenever 1=Pr[P = 1] > 0.

Suppose we are given a \mathsf{PostBQP} family of circuits to decide a language L. We assume without loss of generality (e. g. see the inessential properties of quantum computers) that all gates have transition matrices that are represented with real numbers, at the expense of adding one more qubit. Let Ψ denote the final quantum state of the circuit before the postselecting measurement is made. The overall goal of the proof is to construct a \mathsf{PP} algorithm to decide L. More specifically it suffices to have L correctly compare the squared amplitude of Ψ in the states with 1=Q = 1, P = 1 to the squared amplitude of Ψ in the states with 1=Q = 0, P = 1 to determine which is bigger. The key insight is that the comparison of these amplitudes can be transformed into comparing the acceptance probability of a \mathsf{PP} machine with 1/2.

Let n denote the input size, 1=B = B(n) denote the total number of qubits in the circuit (inputs, ancillary, output and postselection qubits), and 1=G = G(n) denote the total number of gates. Represent the ith gate by its transition matrix Ai (a real unitary matrix) and let the initial state be (padded with zeroes). Then Define S1 (resp. S0) to be the set of basis states corresponding to 1=P = 1, Q = 1 (resp. 1=P = 1, Q = 0) and define the probabilities

The definition of \mathsf{PostBQP} ensures that either or according to whether x is in L or not. Our \mathsf{PP} machine will compare and In order to do this, we expand the definition of matrix multiplication:

where the sum is taken over all lists of G basis vectors Now and can be expressed as a sum of pairwise products of these terms. Intuitively, we want to design a machine whose acceptance probability is something like , since then would imply that the acceptance probability is , while would imply that the acceptance probability is .

The definition of \mathsf{PostBQP} tells us that if x is in L, and that otherwise Let us replace all entries of A by the nearest fraction with denominator for a large polynomial f(n) that we presently describe. What will be used later is that the new values satisfy if x is in L, and if x is not in L. Using the earlier technical assumption and by analyzing how the 1 norm of the computational state changes, this is seen to be satisfied if thus clearly there is a large enough f that is polynomial in n.

Let , which is the center of , and let be orthogonal to Any qubit in , when measured in the basis , gives the value less than 1/2 of the time. On the other hand, if and we had picked then measuring in the basis would give the value all of the time. Since we don't know s we also don't know the precise value of r*, but we can try several (polynomially many) different values for in hopes of getting one that is "near" r*. Specifically, note and let us successively set to every value of the form for Then elementary calculations show that for one of these values of i, the probability that the measurement of in the basis yields is at least

Overall, the \mathsf{PostBQP} algorithm is as follows. Let k be any constant strictly between 1/2 and We do the following experiment for each : construct and measure in the basis a total of times where C is a constant. If the proportion of measurements is greater than k, then reject. If we don't reject for any i, accept. Chernoff bounds then show that for a sufficiently large universal constant C, we correctly classify x with probability at least 2/3. Note that this algorithm satisfies the technical assumption that the overall postselection probability is not too small: each individual measurement of has postselection probability and so the overall probability is .