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).
Contents
- Basic properties
- PostBQP PP
- Proving PostBQP PP
- Matrix view of PostBQP algorithms
- Technicality we may assume entries of the transition matrices Ai are rationals with denominator 2 f n displaystyle 2fn for some polynomial fn
- Constructing the PP machine
- Proving PP PostBQP
- Aaronsons algorithm
- Analysis
- Implications
- References
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:
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:
Basic properties
In order to describe some of the properties of PostBQP we fix a formal way of describing quantum postselection. Define a quantum algorithm to be a family of quantum circuits (specifically, a uniform circuit family). We designate one qubit as the postselection qubit P and another as the output qubit Q. Then PostBQP is defined by postselecting upon the event that the postselection qubit is |1>. Explicitly, a language L is in PostBQP if there is a quantum algorithm A so that after running A on input x and measuring the two qubits P and Q,
One can show that allowing a single postselection step at the end of the algorithm (as described above) or allowing intermediate postselection steps during the algorithm are equivalent.
Here are three basic properties of PostBQP (which also hold for BQP via similar proofs):
1. PostBQP is closed under complement. Given a language L in PostBQP and a corresponding deciding circuit family, create a new circuit family by flipping the output qubit after measurement, then the new circuit family proves the complement of L is in PostBQP.
2. You can do probability amplification in PostBQP. The definition of PostBQP is not changed if we replace the 2/3 value in its definition by any other constant strictly between 1/2 and 1. As an example, given a PostBQP algorithm A with success probability 2/3, we can construct another algorithm which runs three independent copies of A, outputs a postselection bit equal to the conjunction of the three "inner" ones, and outputs an output bit equal to the majority of the three "inner" ones; the new algorithm will be correct with conditional probability
3. PostBQP is closed under intersection. Suppose we have PostBQP circuit families for two languages L1 and L2, with respective postselection qubits and output qubits P1, P2, Q1, Q2. We may assume by probability amplification that both circuit families have success probability at least 5/6. Then we create a composite algorithm where the circuits for L1 and L2 are run independently, and we set P to the conjunction of P1 and P2, and Q to the conjunction of Q1 and Q2. It is not hard to see by a union bound that this composite algorithm correctly decides membership in
More generally, combinations of these ideas show that PostBQP is closed under union and BQP truth-table reductions.
PostBQP = PP
Scott Aaronson showed that the complexity classes PostBQP (postselected bounded error quantum polynomial time) and PP (probabilistic polynomial time) are equal. The result was significant because this quantum computation reformulation of PP gave new insight and simpler proofs of properties of PP.
The usual definition of a 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 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 PostBQP as follows: we require that Pr[P = 1] ≥ 2−nc for some constant c depending on the circuit family. Note this choice does not affect the basic properties of PostBQP, and also it can be shown that any computation consisting of typical gates (e.g. Hadamard, Toffoli) has this property whenever Pr[P = 1] > 0.
Proving PostBQP ⊆ PP
Suppose we are given a 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
Matrix view of PostBQP algorithms
Let n denote the input size, B = B(n) denote the total number of qubits in the circuit (inputs, ancillary, output and postselection qubits), and G = G(n) denote the total number of gates. Represent the ith gate by its transition matrix Ai (a real unitary
The definition of PostBQP ensures that either
Our PP machine will compare
where the sum is taken over all lists of G basis vectors
Technicality: we may assume entries of the transition matrices Ai are rationals with denominator 2 f ( n ) {displaystyle 2^{f(n)}} for some polynomial f(n).
The definition of PostBQP tells us that
Constructing the PP machine
Now we provide the detailed implementation of our PP machine. Let
then
We define our PP machine to
Then it is straightforward to compute that this machine accepts with probability
Proving PP ⊆ PostBQP
Suppose we have a PP machine with time complexity T:=T(n) on input x of length n := |x|. Thus the machine flips a coin at most T times during the computation. We can thus view the machine as a deterministic function f (implemented, e.g. by a classical circuit) which takes two inputs (x, r) where r, a binary string of length T, represents the results of the random coin flips that are performed by the computation, and the output of f is 1 (accept) or 0 (reject). The definition of PP tells us that
Thus, we want a PostBQP algorithm that can determine whether the above statement is true.
Define s to be the number of random strings which lead to acceptance,
and so
Aaronson's algorithm
Aaronson's algorithm for solving this problem is as follows. For simplicity, we will write all quantum states as unnormalized. First, we prepare the state
Where H denotes the Hadamard gate, we compute the state
Where
Visualizing the possible states of a qubit as a circle, we see that if
Analysis
Let
Specifically, note
Overall, the PostBQP algorithm is as follows. Let k be any constant strictly between 1/2 and
Note that this algorithm satisfies the technical assumption that the overall postselection probability is not too small: each individual measurement of