Royal Society Publishing

Quantum computing, postselection, and probabilistic polynomial-time

Scott Aaronson

Abstract

I study the class of problems efficiently solvable by a quantum computer, given the ability to ‘postselect’ on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.

Keywords:

1. Introduction

Postselection is the power of discarding all runs of a computation in which a given event does not occur. To illustrate, suppose we are given a Boolean formula in a large number of variables, and we wish to find a setting of the variables that makes the formula true. Provided such a setting exists, this problem is easy to solve using postselection: we simply set the variables randomly, then postselect on the formula being true.

This paper studies the power of postselection in a quantum computing context. I define a new complexity class called PostBQP (postselected bounded-error quantum polynomial-time), which consists of all problems solvable by a quantum computer in polynomial time, given the ability to postselect on a measurement yielding a specific outcome. The main result is that PostBQP equals the well-known classical complexity class PP (probabilistic polynomial-time). Here PP is the class of problems for which there exists a probabilistic polynomial-time Turing machine that accepts with probability greater than 1/2 if and only if the answer is ‘yes.’ For example, given a Boolean formula, a PP machine can decide whether the majority of settings to the variables make the formula true. Indeed, this problem turns out to be PP-complete (that is, among the hardest problems in PP).1

The motivation for the PostBQP=PP result comes from two quite different sources. The original motivation was to analyse the computational power of ‘fantasy’ versions of quantum mechanics, and thereby gain insight into why quantum mechanics is the way it is. In particular, §4 will show that if we changed the measurement probability rule from |ψ|2 to |ψ|p for some p≠2, or allowed linear but non-unitary evolution, then we could simulate postselection, and thereby solve PP-complete problems in polynomial time. If we consider such an ability extravagant, then we might take these results as helping to explain why quantum mechanics is unitary, and why the measurement rule is |ψ|2.

A related motivation comes from an idea that might be called anthropic computing—arranging things so that we are more likely to exist if a computer produces a desired output than if it does not. As a simple example, under the many-worlds interpretation of quantum mechanics, we might kill ourselves in all universes where a computer fails! My result implies that, using this ‘technique’, we could solve not only NP-complete problems efficiently, but PP-complete problems as well.

However, the PostBQP=PP result also has a more unexpected implication. One reason to study quantum computing is to gain a new, more general perspective on classical computer science. By analogy, many famous results in computer science involve only deterministic computation, yet it is hard to imagine how anyone could have proved these results had researchers not long ago ‘taken aboard’ the notion of randomness.2 Likewise, taking quantum mechanics aboard has already led to some new results about classical computation (Kerenidis & de Wolf 2003; Aaronson 2004b; Aharonov & Regev 2004). What this paper will show is that, even when classical results are already known, quantum computing can sometimes provide new and simpler proofs for them.

When Gill (1972, 1977) defined PP, he also asked a notorious question that remained open for 18 years: is PP closed under intersection?3 In other words, given two probabilistic polynomial-time Turing machines A and B, does there exist another such machine that accepts with probability greater than 1/2 if and only if A and B both do? The question was finally answered in the affirmative by Beigel et al. (1995), who introduced a brilliant technique for representing the logical AND of two majority functions by the sign of a low-degree rational function. Fortnow & Reingold (1996) later extended the technique to show that PP is closed under ‘polynomial-time truth-table reductions’. This means that a polynomial-time turing machine that makes non-adaptive queries to a PP oracle is no more powerful than PP itself. (Note that a query is ‘non-adaptive’ if it does not depend on the answers to previous queries. Beigel (1994) has given evidence that the Fortnow–Reingold result does not generalize to adaptive queries.)

Now the class PostBQP is trivially closed under intersection, as well as under polynomial-time truth-table reductions. So the fact that PostBQP=PP immediately implies the (Beigel et al. 1995) and (Fortnow & Reingold 1996) results. Indeed, it even implies that PP is closed under quantum polynomial-time truth-table reductions, which seems to be a new result. In my view, the PostBQP=PP proof is conceptually simpler than Beigel et al.'s original proof, since (for example) it makes no explicit use of rational functions. (Although, as pointed out to me by Richard Beigel, a result on rational functions similar to those in (Beigel et al. 1995) could be extracted from the proof of my result.)

This paper is based on chapter 15 of my PhD thesis (Aaronson 2005). Some of the results appeared in preliminary form in (Aaronson 2004), before I made the connection to showing PP closed under intersection.

2. Related work

Besides PostBQP, several other ‘non-deterministic’ versions of BQP have appeared in the literature. Adleman et al. (1997) defined NQP to be the class of problems for which there exists a polynomial-time quantum algorithm that accepts with non-zero probability if and only if the answer is ‘yes.’ Then, in a result reminiscent of this paper's, Fenner et al. (1999) showed that NQP equals a classical class called coC=P.4 Also, Watrous (2000) defined QMA as the class of problems for which a polynomial-time quantum verifier can be convinced of a ‘yes’ answer by a polynomial-size quantum proof. If we require the proof to be classical, then we obtain the apparently weaker class QCMA, defined by Aharonov & Naveh (2002). Note that all of these classes are contained in PP (Watrous 2000), and hence in PostBQP.

The idea of postselection has recurred several times in quantum computing. For example, Terhal & DiVincenzo (2004) used postselection to show that constant-depth quantum circuits are probably hard to simulate, and (Aaronson 2005b) used it to show that BQP/qpoly⊆PP/poly (that is, any problem solvable in BQP with polynomial-size quantum advice, is also solvable in PP with polynomial-size classical advice).

If we add postselection to a classical probabilistic polynomial-time Turing machine, then we obtain a complexity class known as BPPpath, which was defined by Han et al. (1997), and which sits somewhere between MA and PP (MA being a probabilistic generalization of NP).

Fortnow (2002) reports that in 1990, he, Fenner and Kurtz tried to show PP closed under intersection by (i) defining a seemingly weaker class, (ii) showing that class closed under intersection and then (iii) showing that it actually equals PP. The attempt failed, and soon thereafter Beigel et al. (1995) succeeded with a quite different approach. This paper could be seen as a vindication of Fortnow et al.'s original approach—all it was missing was quantum mechanics! Admittedly, Li (1993) gave another proof along Fortnow et al.'s lines in 1993. However, Li's proof makes heavy use of rational functions, and seems less intuitive than the one here.

3. The class PostBQP

In what follows, I assume basic familiarity with quantum computing, and in particular with the class BQP (bounded-error quantum polynomial time) defined by Bernstein & Vazirani (1997). It is now time to define PostBQP more formally.

PostBQP is the class of languages L⊆{0,1}* for which there exists a uniform family of polynomial-size quantum circuits {Cn}n≥1 such that for all inputs x,

  1. after Cn is applied to the state |0…0〉⊗|x, the first qubit has a non-zero probability of being measured to be |1〉;

  2. if xL, then conditioned on the first qubit being |1〉, the second qubit is |1〉 with probability at least 2/3;

  3. if x∉L, then conditioned on the first qubit being |1〉, the second qubit is |1〉 with probability at most 1/3.

Here ‘uniform’ means that there exists a classical algorithm that outputs a description of Cn in time polynomial in n. Note that, by a result of Shi (2002), we can assume without loss of generality that Cn is composed only of Hadamard and Toffoli gates. (This is true even for a postselected quantum circuit, since by the Solovay–Kitaev theorem (Kitaev 1997), we can achieve the needed accuracy in amplitudes at the cost of a polynomial increase in circuit size.)

It is easy to see that NP⊆PostBQP. For given a Boolean formula ϕ with n variables, to decide whether ϕ has any satisfying assignments we can first generate the stateEmbedded Imagewhere ϕ(x)=1 if the assignment x satisfies ϕ and ϕ(x)=0 otherwise. We then postselect on the first qubit being |1〉. If ϕ has no satisfying assignments, then the second qubit will be |0〉 with certainty; while if ϕ has one or more satisfying assignments, then the second qubit will be |1〉 with probability at least 1–2n.

To show PostBQP⊆PP, we can use the same observations used by Adleman et al. (1997) to show that BQP⊆PP, but sum only over paths where the first qubit is |1〉 at the end. This is given in more detail in the following.

PostBQP⊆PP.

Assume that our quantum circuit is composed of Hadamard and Toffoli gates. Then the final amplitude αz of each basis state |z〉 can be written as a sum of exponentially many contributions, call them az,1,…,az,N, each of which is a rational real number computable in classical polynomial time. So the final probability of |z〉 equalsEmbedded ImageWe need to test which is greater: the sum S0 of Embedded Image over all z beginning with 10, or the sum S1 of Embedded Image over all z beginning with 11. We can do this in PP as follows. For k∈{0,1}, letEmbedded ImageEmbedded ImageThen Embedded Image and Embedded Image. So to test whether S0>S1, it suffices to test whether Embedded Image. Note that Embedded Image and Embedded Image are both sums of non-negative terms, and thus are representable as the number of accepting and rejecting paths respectively of a PP machine (times some normalizing constant). ▪

How robust is PostBQP? Just as Bernstein & Vazirani (1997) showed that intermediate measurements do not increase the power of ordinary quantum computers, so it is easily shown that intermediate postselection steps do not increase the power of PostBQP. Whenever we want to postselect on a qubit j being |1〉, we simply apply a CNOT gate from j into a fresh ancilla qubit that is initialized to |0〉 and that will never be written to again. Then, at the end, we compute the AND of the ancilla qubits, and swap the result into the first qubit. By a standard Chernoff bound, it follows that we can repeat a PostBQP computation a polynomial number of times, and thereby reduce the error probability from 1/3 to 1–2p(n) for any polynomial p.

A corollary of the above observations is that PostBQP has strong closure properties.

PostBQP is closed under union, intersection, and complement. Indeed, it is closed under BQP truth-table reductions. This means that Embedded Image, where Embedded Image is the class of problems solvable by a machine that can make a polynomial number of non-adaptive classical queries to a PostBQP oracle, followed by a polynomial-time quantum computation.

Clearly PostBQP is closed under complement, since the definition is symmetric with respect to xL and x∉L. For closure under intersection, let L1, L2∈PostBQP; then we need to decide whether xL1L2. Run amplified computations (with error probability at most 1/6) to decide if xL1 and if xL2, postselect on both computations succeeding, and accept if and only if both accept. It follows that PostBQP is closed under union as well. In general, suppose a Embedded Image machine M submits queries q1,…,qp(n) to the PostBQP oracle. Then run amplified computations (with error probability at most, say, Embedded Image) to decide the answers to these queries, and postselect on all p(n) of them succeeding. By the union bound, if M had error probability ϵ with a perfect PostBQP oracle, then its new error probability is at most ϵ+1/10, which can easily be reduced through amplification.▪

One might wonder why proposition 3.3 does not go through with adaptive queries. The reason is subtle: suppose we have two PostBQP computations, the second of which relies on the output of the first. Then even if the first computation is amplified a polynomial number of times, it still has an exponentially small probability of error. But since the second computation uses postselection, any non-zero error probability could be magnified arbitrarily, and is therefore too large.

I now prove the main result.

PostBQP=PP.

We have already observed that PostBQP⊆PP. For the other direction, let f: {0,1}n→{0,1} be an efficiently computable Boolean function, and let s=|{x: f(x)=1}|. Then we need to decide in PostBQP whether s<2n−1 or s≥2n−1. (As a technicality, we can guarantee using padding that s>0.)

The algorithm is as follows: first prepare the state Embedded Image. Then following Abrams & Lloyd (1998), apply Hadamard gates to all n qubits in the first register and postselect5 on that register being |0〉n. This produces the state |0〉n|ψ〉, whereEmbedded ImageNext, for some positive real numbers α, β to be specified later, prepare α|0〉|ψ〉+β|1〉H|ψ〉, where

Embedded Imageis the result of applying a Hadamard gate to |ψ〉. Then postselect on the second qubit being |1〉. This yields the reduced stateEmbedded Imagein the first qubit.

Suppose s<2n−1, so that s and Embedded Image are both at least 1. Then we claim there exists an integer i∈[−n, n] such that, if we set β/α=2i, then Embedded Image is close to the state Embedded Image:Embedded ImageFor since Embedded Image lies between 2n and 2n, there must be an integer i∈[−n,n−1] such that Embedded Image and Embedded Image fall on opposite sides of |+〉 in the first quadrant (see figure 1). So the worst case is that Embedded Image, which occurs when Embedded Image and Embedded Image. On the other hand, suppose s≥2n−1, so that Embedded Image. Then Embedded Image never lies in the first or third quadrants, and therefore Embedded Image.

Figure 1

If s and 2n−2s are both positive, then as we vary the ratio of β to α, we eventually get close to Embedded Image (dashed lines). On the other hand, if 2n−2s is not positive (dotted line), then we never even get into the first quadrant.

It follows that, by repeating the whole algorithm n(2n+1) times (as in proposition 3.3), with n invocations for each integer i∈[−n,n], we can learn whether s<2n−1 or s≥2n−1 with exponentially small probability of error. ▪

Combining proposition 3.3 with theorem 3.4 immediately yields that PP is closed under intersection, as well as under BQP truth-table reductions.6

4. Fantasy quantum mechanics

Is quantum mechanics an island in theoryspace? By ‘theoryspace’, I mean the space of logically conceivable physical theories, with two theories close to each other if they differ in few respects. An ‘island’ in theoryspace is then a natural and interesting theory, whose neighbors are all somehow perverse or degenerate. The Standard Model is not an island, because we do not know of any compelling (non-anthropic) reason why the masses and coupling constants should have the values they do. Likewise, general relativity is probably not an island, because of alternatives such as the Brans–Dicke theory.

To many physicists, however, quantum mechanics does seem like an island: change any one aspect, and the whole theory becomes inconsistent or non-sensical. There are many mathematical results supporting this opinion: for example, Gleason's theorem (Gleason 1957) and other ‘derivations’ of the |ψ|2 probability rule (Deutsch 1999; Zurek 2003); arguments for why amplitudes should be complex numbers, as opposed to (say) real numbers or quaternions (Caves et al. 2002; Hardy 2003; Aaronson 2004); and ‘absurd’ consequences of allowing nonlinear transformations between states (Gisin 1990; Polchinski 1991). The point of these results is to provide some sort of explanation for why quantum mechanics has the properties it does.

Abrams & Lloyd (1998) suggested that computational complexity could also be pressed into such an explanatory role. In particular, they showed that under almost any nonlinear variant of quantum mechanics, one could build a ‘nonlinear quantum computer’ able to solve NP-complete and even #P-complete problems in polynomial time.7 One interpretation of their result is that we should look very hard for nonlinearities in experiments! But a different interpretation, the one I prefer, is that their result provides independent evidence that quantum mechanics is linear.

This section builds on theorem 3.4 to offer similar ‘evidence’ that quantum mechanics is unitary, and that the measurement rule is |ψ|2.

Let BQPnu be the class of problems solvable by a uniform family of polynomial-size, bounded-error quantum circuits, where the circuits can consist of arbitrary 1- and 2-qubit invertible linear transformations, rather than just unitary transformations. Immediately before a measurement, the amplitude αx of each basis state |x〉 is divided by Embedded Image to normalize it.

BQPnu=PP.

The inclusion BQPnu⊆PP follows easily from Adleman et al.'s (1997) proof that BQP⊆PP, which does not depend on unitarity. For the other direction, by theorem 3.4 it suffices to show that PostBQP⊆BQPnu. To postselect on a qubit being |1〉, simply apply the 1-qubit non-unitary operationEmbedded Imagefor some sufficiently large polynomial q. ▪

Next, for any non-negative real number p, define BQPp similarly to BQP, except that when we measure, the probability of obtaining a basis state |x〉 equals Embedded Image rather than |αx|2. Thus BQP2=BQP. Assume that all gates are unitary and that there are no intermediate measurements, just a single standard-basis measurement at the end.

PP⊆BQPp⊆PSPACE for all constants p≠2, with BQPp=PP when p∈{4, 6, 8,…}.

To simulate PP in BQPp, run the algorithm of theorem 3.4, having initialized O(n2q(n)/|2−p|) ancilla qubits to |0〉 for some sufficiently large polynomial q. Suppose the algorithm's state at some point is Embedded Image, and we want to postselect on the event Embedded Image, where Embedded Image is a subset of basis states. Here is how: if p<2, then apply Hadamard gates to K=2q (n)/(2−p) fresh ancilla qubits conditioned on Embedded Image. The result is to increase the ‘probability mass’ of each Embedded Image from |αz|p to

Embedded Imagewhile the probability mass of each Embedded Image remains unchanged. Similarly, if p>2, then apply Hadamard gates to K=2q (n)/(p−2) fresh ancilla qubits conditioned on Embedded Image. This decreases the probability mass of each Embedded Image from |αz|p to 2K.|2K/2αz|p=2q(n)|αz|p, while the probability mass of each Embedded Image remains unchanged. The final observation is that theorem 3.4 still goes through if p≠2. For it suffices to distinguish the case Embedded Image from Embedded Image with exponentially small probability of error, using polynomially many copies of the state Embedded Image. But we can do this for any p, since all |ψ|p rules behave well under tensor products (in the sense that |αβ|p=|α|p|β|p).

To simulate BQPp in PP when p∈{4, 6, 8,…}, we generalize the result of Adleman et al. (1997), which handled the case p=2. As in proposition 3.2, we can write each amplitude αz as a sum of exponentially many contributions, Embedded Image, where each az,i is a rational real number computable in classical polynomial time. Then letting S be the set of accepting states, it suffices to test whetherEmbedded Imageis greater than Embedded Image. We can do this in PP by separating out the positive and negative contributions Embedded Image, exactly as in proposition 3.2.▪

5. Open problems

What other classical complexity classes can we characterize in quantum terms, and what other questions can we answer by that means? A first step might be to prove even stronger closure properties for PP. For example, let Embedded Image be the class of problems solvable by a BQP machine that can make a single quantum query, which consists of a list of polynomially many questions for a PostBQP oracle. Then does Embedded Image equal PostBQP? The difficulty in showing this seems to be uncomputing garbage qubits after the PostBQP oracle is simulated.

As for fantasy quantum mechanics, an interesting open question is whether BQPp=PP for all non-negative real numbers p≠2. A natural idea for simulating BQPp in PP would be to use a Taylor series expansion for the probability masses |αx|p. Unfortunately, I have no idea how to get fast enough convergence.

Acknowledgments

I thank Avi Wigderson for helpful discussions, Richard Beigel and Lance Fortnow for correspondence, and the anonymous reviewers for their comments. This work was begun while I was a graduate student at UC Berkeley, supported by an NSF Graduate Fellowship, and completed during a postdoc at the Institute for Advanced Study in Princeton.

Footnotes

  • See the ‘Complexity Zoo’ (www.complexityzoo.com) for more information about the complexity classes mentioned in this paper.

  • A few examples are primality testing in deterministic polynomial time (Agrawal et al. 2004), undirected graph connectivity in log-space (Reingold 2005), and inapproximability of the 3-SAT problem unless P=NP (Håstad 2001).

  • It is clear that PP is closed under complement, so this question is equivalent to asking whether PP is closed under union.

  • Unfortunately, I do not know of any classical result that this helps to prove. That coC=P is closed under union and intersection is obvious.

  • Postselection is actually overkill here, since the first register has at least 1/4 probability of being |0〉n.

  • Another corollary is a result of Fortnow & Rogers (1999), that BQP is ‘low’ for PP, that is, PPBQP=PP. For clearly PostBQPBQP=PostBQP.

  • A caveat is that it remains an open problem whether this can be done fault-tolerantly. The answer might depend on the allowed types of nonlinear gate. On the other hand, if arbitrary 1-qubit nonlinear gates can be implemented without error, then even PSPACE-complete problems can be solved in polynomial time. This is tight, since nonlinear quantum computers are not hard to simulate in PSPACE.

    • Received December 23, 2004.
    • Accepted July 4, 2005.

References

View Abstract