PostBQP and Quantum Postselection

$\mathsf{PostBQP}$ is what you get by handing an ordinary bounded-error quantum computer one science-fiction privilege: alongside its answer qubit it may designate a postselection qubit, and it is allowed to declare, by fiat, that this qubit was measured and found to be $|1\rangle$ — even when that outcome had exponentially small probability. Every branch of the wavefunction in which the postselection qubit came out $|0\rangle$ is simply discarded, and the surviving sliver is renormalized to weight one. No physical device can do this; realizing it would mean either reversing a measurement or repeating an experiment an astronomical number of times until a near-impossible event fires. Yet as a proof device the model is clean, robust, and startlingly strong. The headline, proved by Scott Aaronson in 2004, is a single exact equality: $\mathsf{PostBQP}=\mathsf{PP}$ . Here $\mathsf{PP}$ — probabilistic polynomial time — is the counting class that decides whether a signed sum of exponentially many $\pm 1$ contributions is positive, and by Toda's theorem it towers over the entire polynomial hierarchy ( $\mathsf{PH}\subseteq\mathsf{P}^{\mathsf{PP}}$ ). That a one-line augmentation of $\mathsf{BQP}$ leaps all the way to $\mathsf{PP}$ is the surprise, and Aaronson's proof is bidirectional and short. One direction refines the Feynman path-sum used for $\mathsf{BQP}\subseteq\mathsf{PP}$ , tracking the postselected normalization as a ratio of two exponential sums; the other encodes a $\#\mathsf{P}$ counting threshold into a single qubit's amplitude and uses a postselected rotation to amplify its sign to constant bias. The payoff is the rigorous backbone of quantum-supremacy theory. If a classical computer could efficiently sample from an arbitrary quantum circuit's output distribution, classical postselection would inherit quantum postselection's power, forcing $\mathsf{PostBPP}=\mathsf{PostBQP}=\mathsf{PP}$ — and since $\mathsf{PostBPP}$ sits low in the hierarchy, $\mathsf{PH}$ would collapse. This is the engine behind BosonSampling and IQP hardness.

Key takeaways

$\mathsf{PostBQP}$ is $\mathsf{BQP}$ plus the unphysical power to condition a computation on a designated qubit being $|1\rangle$ , an event whose probability may be exponentially small.
Aaronson's theorem (2004) is the exact equality $\mathsf{PostBQP}=\mathsf{PP}$ — a one-line change to $\mathsf{BQP}$ climbs all the way to the counting class $\mathsf{PP}$ .
The mechanism is renormalization: throwing away almost all the probability mass and rescaling the surviving branch turns an exponentially small amplitude difference — the sign of a $\mathsf{GapP}$ sum — into an order-one bias, which is exactly what $\mathsf{PP}$ decides.
As a two-paragraph corollary it reproves that $\mathsf{PP}$ is closed under intersection and union, a fact whose original combinatorial proof (Beigel–Reingold–Spielman) was a tour de force.
Because efficient classical sampling would give $\mathsf{PostBPP}=\mathsf{PostBQP}=\mathsf{PP}\subseteq\mathsf{PH}$ and collapse the hierarchy, postselection underpins BosonSampling and IQP sampling-hardness.
Key idea: Postselection turns the renormalization of an exponentially rare measurement branch into free computational power — ratios of exponential sums that $\mathsf{BQP}$ cannot resolve become decidable, and the resulting class is exactly $\mathsf{PP}$ .

The core insight

Postselection turns the renormalization of an exponentially rare measurement branch into free computational power: ratios of exponential sums that $\mathsf{BQP}$ cannot resolve become decidable, and the resulting class is exactly the counting class $\mathsf{PP}$ .

Where this lives today

Postselection is the load-bearing beam of quantum-supremacy theory, the rigorous reason sampling experiments are believed hard to fake classically. Aaronson and Arkhipov's BosonSampling (2011) sends indistinguishable photons through a linear-optical network and samples the output; the output probabilities are squared permanents of complex matrices, and computing permanents is $\#\mathsf{P}$ -hard. Their argument runs exactly along the second figure: an efficient classical sampler, granted postselection, would place the sign of a permanent inside $\mathsf{PostBPP}\subseteq\mathsf{PH}$ , but via $\mathsf{PostBQP}=\mathsf{PP}$ and Toda's theorem that collapses the hierarchy. The same template, instantiated with commuting "instantaneous quantum polynomial-time" (IQP) circuits by Bremner, Jozsa and Shepherd, needs only a constant-depth nonuniversal model, because postselected IQP already equals $\mathsf{PostBQP}$ . These arguments framed how Google's 2019 Sycamore random-circuit-sampling claim and later demonstrations are judged: the debate over "how supreme" an experiment is becomes a debate over how well the ideal distribution is reproduced and how far classical spoofing and tensor-network simulation can be pushed. On the theory side, $\mathsf{PostBQP}=\mathsf{PP}$ is a hub in the modern map — it neighbours $\mathsf{QMA}\subseteq\mathsf{PP}$ , the celebrated $\mathsf{QIP}=\mathsf{PSPACE}$ , and open questions like whether $\mathsf{BQP}\subseteq\mathsf{PH}$ , which the 2019 Raz–Tal oracle separation suggests may fail.

The physical picture

An ordinary quantum computation is a giant interference experiment whose final amplitudes are exponential sums, and $\mathsf{BQP}$ can only read off the probability of an answer when there is a constant gap around one-half. Tiny differences between exponential sums are invisible, buried under normalization. Postselection changes the rules: you are allowed to throw away almost all of the probability mass — every "boring" branch in which the flag qubit read $|0\rangle$ — and renormalize whatever sliver survives. An exponentially small signal, once it is the whole of what remains, becomes order-one. Detecting the sign of an exponential sum is precisely what $\mathsf{PP}$ does, so the renormalization is the extra power. The first figure makes that mechanism concrete on a single computation.

Figure

Postselection discards the p equals 0 branch and renormalizes the surviving sliver: even when the kept branch has probability ε as small as 2⁻ⁿ, conditioning rescales it to weight one, so a conditional acceptance Pr(o=1 given p=1) = 0.8 becomes order-one and readable, though the raw Pr(o=1) = 0.19 would have said reject

The reason this is so much power, and not merely a rescaling, is that the surviving bias can encode the sign of a counting problem. Aaronson's second insight runs the argument backwards: any $\mathsf{PP}$ question "is $s>2^{n-1}$ ?" about a count $s=\#\{x:f(x)=1\}$ can be pressed into a single qubit's amplitude, and a postselected rotation magnifies which side of the threshold $s$ lies on into a constant, machine-readable gap. But the equality has a sharp ceiling — $\mathsf{PP}\subseteq\mathsf{PSPACE}$ , and by Toda's theorem the whole polynomial hierarchy reduces to $\mathsf{PP}$ — and its most-used consequence is a contrapositive: efficient classical simulation of quantum sampling would drag $\mathsf{PP}$ down into the low levels of $\mathsf{PH}$ and collapse it. The second figure is that collapse argument, the rigorous skeleton of quantum-supremacy proofs.

Figure

The sampling-hardness collapse: PostBQP = PP by Aaronson, proved ⊆ by the Feynman path-sum and ⊇ by a postselected rotation; if a classical sampler could copy a quantum circuit then classical postselection gives PostBPP = PP, but PostBPP ⊆ Σ₃ᵖ ⊆ PH while Toda gives PH ⊆ Pᴾᴾ, so PP ⊆ PH forces the polynomial hierarchy to collapse

The core equations

A $\mathsf{PostBQP}$ machine is an ordinary uniform family of polynomial-size quantum circuits with two distinguished qubits: an output qubit $o$ and a postselection qubit $p$ . Membership is defined not by the raw statistics but by the statistics conditioned on $p=1$ , an event we are promised is possible but which may be vanishingly rare.

L\in\mathsf{PostBQP}\iff \exists\,\{C_n\}\ \text{poly-size, output }o,\ \text{postselect }p \qquad (1)

where: $C_n$ — uniformly generated polynomial-size quantum circuit on the input plus $\mathrm{poly}(n)$ ancillas; $p$ — designated postselection qubit, on which we condition the outcome $p=1$ ; $o$ — output qubit, measured after postselection to read accept or reject. Reading it: the model differs from $\mathsf{BQP}$ by one word — "condition on $p=1$ " — and everything downstream flows from that word. The acceptance rule is a bounded-error promise, but on the conditional distribution. The postselection probability must be nonzero, yet it is explicitly permitted to be exponentially small — that permission is the whole source of the extra power.

\Pr[p=1]>0,\qquad \Pr[o=1\mid p=1]\;\begin{cases}\ge 2/3 & x\in L\\[2pt] \le 1/3 & x\notin L\end{cases} \qquad (2)

where: $\Pr[p=1]$ — probability the postselection event occurs, required positive but possibly $2^{-\mathrm{poly}(n)}$ ; $\Pr[o=1\mid p=1]$ — conditional acceptance probability; $2/3,\,1/3$ — thresholds, replaceable by any constants with a gap, or even $1/2\pm 2^{-\mathrm{poly}}$ after amplification. Reading it: only the sign of $\Pr[o=1\mid p=1]-1/2$ is being asked for, but conditioning lets that sign carry an exponential amount of information. The central identity states that this idealized model captures exactly the counting class $\mathsf{PP}$ . It is an equality, not a containment — both directions are proved.

\boxed{\;\mathsf{PostBQP}=\mathsf{PP}\;} \qquad (3)

where: $\mathsf{PP}$ — the class of languages $L$ decided by a poly-time probabilistic machine accepting with probability strictly greater than $1/2$ iff $x\in L$ (unbounded error: the gap may be exponentially small). Reading it: the quantum model with a physically forbidden resource equals a purely classical counting class, so each becomes a tool for reasoning about the other. The entire physical content of postselection is one map on states: project onto $p=1$ and renormalize. There is no unitary that does this; it is measurement collapse with the "wrong" branch selected on demand.

|\psi_{\mathrm{post}}\rangle=\frac{(\,I\otimes|1\rangle\langle1|_p\,)\,|\psi\rangle}{\big\|\,(\,I\otimes|1\rangle\langle1|_p\,)\,|\psi\rangle\,\big\|} \qquad (4)

where: $|\psi\rangle$ — full pre-measurement register state; $|1\rangle\langle1|_p$ — projector onto $p=1$ ; the denominator $\|\cdot\|=\sqrt{\Pr[p=1]}$ — the renormalization that can blow up an exponentially small numerator. Reading it: dividing by a possibly exponentially small norm is what magnifies a faint amplitude difference into an order-one state — this single line is the mechanism of the whole article. For the $\mathsf{PostBQP}\subseteq\mathsf{PP}$ direction, expand every amplitude as a Feynman path sum over the universal real gate set $\{H,\text{Toffoli}\}$ . Clearing the $1/\sqrt2$ factors turns each amplitude into an integer difference — a $\mathsf{GapP}$ function, the class of differences of $\#\mathsf{P}$ counts.

a_y=\sum_{\text{paths }\gamma:\,0\to y}\ \prod_{t}\langle\gamma_{t+1}|U_t|\gamma_t\rangle\;=\;\frac{P_y-N_y}{2^{m}} \qquad (5)

where: $a_y$ — final amplitude of basis string $|y\rangle$ ; $P_y,\,N_y$ — counts of positive- versus negative-weight paths after clearing denominators; $m$ — the fixed number of $1/\sqrt2$ factors; $P_y-N_y\in\mathsf{GapP}$ . Reading it: a quantum amplitude is literally a signed exponential sum, and $\mathsf{GapP}$ is the algebra of such sums. The postselected acceptance probability is then a ratio of two $\mathsf{GapP}$ sums — numerator over the accepting-and-postselected strings, denominator over all postselected strings. Cross-multiplying against the threshold reduces membership to a single sign test.

\Pr[o=1\mid p=1]=\frac{\displaystyle\sum_{y:\,o=1,\,p=1}|a_y|^2}{\displaystyle\sum_{y:\,p=1}|a_y|^2},\qquad |a_y|^2=\frac{(P_y-N_y)^2}{2^{2m}} \qquad (6)

where: $|a_y|^2$ — a product of $\mathsf{GapP}$ quantities (and $\mathsf{GapP}$ is closed under products), hence itself $\mathsf{GapP}$ after summing over $y$ . Reading it: the promise $\Pr[o=1\mid p=1]\ge 2/3$ becomes $2\sum_{A}|a_y|^2\ge 3\cdot\tfrac13\sum_{B}\cdots$ , i.e. the positivity of one $\mathsf{GapP}$ function — exactly a $\mathsf{PP}$ query. For the reverse direction, encode a $\#\mathsf{P}$ count into a single qubit and detect its threshold with a postselected rotation. The amplitude at $|1\rangle$ after a real rotation $R_\theta$ is a tunable linear combination of the two encoded roots, and postselection zooms in on its sign.

|\phi\rangle\propto\sqrt{2^n-s}\,|0\rangle+\sqrt{s}\,|1\rangle,\qquad \langle1|R_\theta|\phi\rangle=\alpha\sin\theta+\beta\cos\theta \qquad (7)

where: $s=\#\{x:f(x)=1\}$ — the count to compare against $2^{n-1}$ ; $\alpha\propto\sqrt{2^n-s},\ \beta\propto\sqrt{s}$ — the encoded amplitudes; $R_\theta=\big(\begin{smallmatrix}\cos\theta&-\sin\theta\\ \sin\theta&\cos\theta\end{smallmatrix}\big)$ — a real rotation. Reading it: the ratio $\beta/\alpha=\sqrt{s/(2^n-s)}$ crosses $1$ exactly at $s=2^{n-1}$ , so postselecting on the difference mode reveals $\mathrm{sgn}(s-2^{n-1})$ . Finally, the equality's most-cited use is the sampling-hardness template. Its logic is a contrapositive that leans on $\mathsf{PostBPP}$ living low in the hierarchy while $\mathsf{PostBQP}$ tops out at $\mathsf{PP}$ .

\mathsf{PostBPP}\subseteq\Sigma_3^{\mathsf p};\quad \text{efficient sampling}\Rightarrow\mathsf{PP}=\mathsf{PostBQP}=\mathsf{PostBPP}\subseteq\mathsf{PH}\;\xRightarrow{\ \text{Toda}\ }\;\mathsf{PH}\text{ collapses} \qquad (8)

where: $\Sigma_3^{\mathsf p}$ — third level of the polynomial hierarchy; $\mathsf{PostBPP}$ (classical postselection) lives here, far below $\mathsf{PP}$ unless $\mathsf{PH}$ collapses. Reading it: the strength of the unphysical quantum model ( $\mathsf{PostBQP}=\mathsf{PP}$ ) is exactly what makes the collapse conclusion strong.

Derivation APostBQP inside PP via the Feynman path sum

The goal is to show that a postselecting quantum machine is no stronger than a classical counting machine, by writing its conditional acceptance probability as a ratio of two $\mathsf{GapP}$ exponential sums and then invoking the defining property of $\mathsf{PP}$ — that it can test the sign of any $\mathsf{GapP}$ function. The only new ingredient beyond the standard $\mathsf{BQP}\subseteq\mathsf{PP}$ argument is carrying the postselected denominator through the calculation and checking that it too stays $\mathsf{GapP}$ , so that comparing numerator and denominator against a constant is a single positivity test. Fix a $\mathsf{PostBQP}$ circuit over the universal real gate set $\{H,\text{Toffoli}\}$ , whose entries lie in $\{0,\pm1,\pm1/\sqrt2\}$ .

Step 1. Expand each final amplitude as a path sum and clear the $1/\sqrt2$ factors: $a_y=(P_y-N_y)/2^{m}$ , where $P_y,N_y$ count positive- and negative-weight computational paths to $|y\rangle$ . Then $P_y-N_y$ is a $\mathsf{GapP}$ function — a difference of two $\#\mathsf{P}$ counts. Why: the only irrational a gate introduces is the Hadamard's $1/\sqrt2$ , and it appears the same number $m$ of times on every path, so it factors out as one global constant, leaving an integer.

Step 2. Square to a probability: $|a_y|^2=(P_y-N_y)^2/2^{2m}$ . Since $\mathsf{GapP}$ is closed under multiplication, $(P_y-N_y)^2$ is $\mathsf{GapP}$ ; the root of two has vanished because $(2^{-m})^2=2^{-2m}$ is a fixed scale. Why: one must work with the probability, not the amplitude — squaring is what removes the irrationality and keeps the arithmetic inside the integer-valued counting classes.

Step 3. Form the conditional over the accepting set $A=\{o=1,p=1\}$ and the postselected set $B=\{p=1\}$ :

\Pr[o=1\mid p=1]=\frac{\sum_{y\in A}|a_y|^2}{\sum_{y\in B}|a_y|^2}.

Both sums are $\mathsf{GapP}$ . Cross-multiplying the promise $\Pr[o=1\mid p=1]\ge 2/3$ gives the single inequality $\sum_{y\in A}|a_y|^2-\tfrac23\sum_{y\in B}|a_y|^2\ge 0$ . Why: the denominator — absent in the plain $\mathsf{BQP}$ proof — is the entire novelty of postselection, and it survives as a $\mathsf{GapP}$ sum, so nothing is lost by conditioning.

Step 4. The left side is a single $\mathsf{GapP}$ function $g(x)$ , and $\mathsf{PP}$ is exactly the class of languages reducible to testing $g(x)\ge 0$ for a $\mathsf{GapP}$ function. Hence $L\in\mathsf{PP}$ , and as the circuit was arbitrary, $\mathsf{PostBQP}\subseteq\mathsf{PP}$ . Why: this is the definition of $\mathsf{PP}$ in $\mathsf{GapP}$ language — the postselected machine has been reduced to a sign query it was built to answer. *The sole addition beyond the standard $\mathsf{BQP}\subseteq\mathsf{PP}$ argument is the postselected denominator $\sum_{y\in B}$ , which remains $\mathsf{GapP}$ .*

Go deeper · Derivation B · 2 minPP inside PostBQP by amplifying a count

Derivation BPP inside PostBQP by amplifying a count

The goal is the surprising direction — that a physically forbidden postselection is powerful enough to solve any counting problem in $\mathsf{PP}$ . The strategy is to reduce a $\mathsf{PP}$ language to deciding whether a $\#\mathsf{P}$ count $s=\#\{x:f(x)=1\}$ exceeds the midpoint $2^{n-1}$ , encode $s$ into the amplitudes of one qubit, and then use a postselected real rotation to inflate the sign of $s-2^{n-1}$ into a constant bias, independent of how narrowly the count clears the threshold. The magic is that postselection can renormalize a difference mode whose weight is exponentially small, so a gap of a single unit in $s$ still produces an order-one answer. Let $f$ be a poly-time predicate.

Step 1. Prepare $\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle|f(x)\rangle$ with $n$ Hadamards followed by the reversible circuit for $f$ ; the flag qubit is then in the state proportional to $\sqrt{2^n-s}\,|0\rangle+\sqrt{s}\,|1\rangle$ . Write $\alpha=\sqrt{(2^n-s)/2^n}$ , $\beta=\sqrt{s/2^n}$ . Why: the uniform superposition converts "how many inputs satisfy $f$ " into a squared amplitude, $\beta^2=s/2^n$ , so the count is now geometric information about one qubit.

Step 2. Note the comparison lives in the ratio $\beta/\alpha=\sqrt{s/(2^n-s)}$ , which exceeds $1$ iff $s>2^{n-1}$ . Equivalently $\mathrm{sgn}(\beta-\alpha)=\mathrm{sgn}(s-2^{n-1})$ . Why: the threshold $s=2^{n-1}$ is exactly the balance point $\alpha=\beta$ of the encoded qubit, so the $\mathsf{PP}$ question becomes "which amplitude is larger?".

Step 3. Apply a real rotation $R_\theta$ , giving $\langle1|R_\theta|\phi\rangle=\alpha\sin\theta+\beta\cos\theta$ , then postselect on a comparison register tuned to kill the common mode $\alpha+\beta$ and keep the difference mode. Sweeping $\theta$ over polynomially many values, Aaronson's construction pushes the conditional bias past $2/3$ when $\beta>\alpha$ and below $1/3$ when $\beta<\alpha$ , whatever the magnitude of $\beta-\alpha$ . Why: postselection renormalizes the tiny surviving amplitude, so an exponentially small $\beta-\alpha$ is rescaled to a constant — this is the renormalization of equation (4) doing computational work.

Step 4. Measuring $o$ after postselection reports $\mathrm{sgn}(s-2^{n-1})$ with bounded error, so $L\in\mathsf{PostBQP}$ ; combined with the previous derivation this gives $\mathsf{PostBQP}=\mathsf{PP}$ . Why: correctness needs only that postselection can condition on the rare aligned branch — no other quantum resource is invoked, which is why the equality is exact. *The identity $\langle1|R_\theta|\phi\rangle=\alpha\sin\theta+\beta\cos\theta$ follows directly from $R_\theta|\phi\rangle=(\alpha\cos\theta-\beta\sin\theta)|0\rangle+(\alpha\sin\theta+\beta\cos\theta)|1\rangle$ .*

Go deeper · Derivation C · 1 minCorollary — PP is closed under intersection

Derivation CCorollary — PP is closed under intersection

The goal is to reprove, in a few lines, a theorem whose original proof (Beigel–Reingold–Spielman, 1991) was a delicate combinatorial construction: that if $L_1,L_2\in\mathsf{PP}$ then $L_1\cap L_2\in\mathsf{PP}$ . The idea is that $\mathsf{PostBQP}$ is obviously closed under intersection — just run two postselecting machines side by side and conjoin their postselections — and since $\mathsf{PostBQP}=\mathsf{PP}$ , the closure transfers to $\mathsf{PP}$ for free. Let $M_1,M_2$ be $\mathsf{PostBQP}$ machines for $L_1,L_2$ with postselect qubits $p_1,p_2$ and outputs $o_1,o_2$ , acting on disjoint ancillas.

Step 1. Run $M_1$ and $M_2$ in parallel and postselect on $p_1=p_2=1$ . Because the registers are disjoint, the conditional factorizes: $\Pr[\cdot\mid p_1=p_2=1]=\Pr_1[\cdot\mid p_1=1]\,\Pr_2[\cdot\mid p_2=1]$ . Why: independence is what makes the joint postselection clean — conditioning on both flags is just the product of conditioning on each.

Step 2. First amplify each machine's conditional acceptance exponentially close to $1$ (on yes) or $0$ (on no) by standard majority-vote repetition inside the postselected branch. Then the product $\Pr_1[o_1=1\mid p_1=1]\cdot\Pr_2[o_2=1\mid p_2=1]$ is close to $1$ iff both accept and close to $0$ otherwise — a valid $\mathsf{PostBQP}$ machine deciding $L_1\cap L_2$ via the joint output $o_1\wedge o_2$ . Why: only after amplification does the product behave like a logical AND; raw two-thirds probabilities would multiply to $4/9$ and blur the decision.

Step 3. Since $\mathsf{PostBQP}=\mathsf{PP}$ , this machine certifies $L_1\cap L_2\in\mathsf{PP}$ ; the union case follows by De Morgan (or a symmetric OR construction). Why: the equality is a two-way bridge — a triviality on the $\mathsf{PostBQP}$ side becomes a hard-won theorem on the $\mathsf{PP}$ side.

Limiting cases

Where $\mathsf{PostBQP}$ sits, and what removing or weakening postselection does to it:

Case	Result	Meaning
No postselection	$\mathsf{BQP}\subseteq\mathsf{PostBQP}=\mathsf{PP}$	Dropping the postselection qubit recovers ordinary $\mathsf{BQP}$ ; since $\mathsf{BQP}\subseteq\mathsf{PP}$ , postselection only adds power and saturates at $\mathsf{PP}$ .
Poly-probability event	collapses to $\mathsf{BQP}$ -like power	Conditioning on a $\Pr[p=1]\ge 1/\mathrm{poly}$ event only rescales by a polynomial factor, leaving the bounded-error structure intact — no jump to $\mathsf{PP}$ .
Classical analogue	$\mathsf{PostBPP}=\mathsf{BPP}_{\mathrm{path}}\subseteq\Sigma_3^{\mathsf{p}}$	Postselected classical computation sits low in $\mathsf{PH}$ ; the quantum version leaps to $\mathsf{PP}$ , and that gap is the engine of supremacy arguments.
Upper ceiling	$\mathsf{PP}\subseteq\mathsf{PSPACE},\quad \mathsf{PH}\subseteq\mathsf{P}^{\mathsf{PP}}$	Toda: $\mathsf{PP}$ is at least as hard as the whole hierarchy, yet is $\mathsf{PSPACE}$ -bounded, so $\mathsf{PostBQP}$ is strong but not unlimited.
Closure corollary	$\mathsf{PP}=\mathsf{PostBQP}\Rightarrow\mathsf{PP}$ closed under $\cap,\cup$	Two machines run in parallel with conjoined postselection give a one-paragraph proof of a once-hard theorem.

Common trapPostBQP = PP means quantum computers can solve PP-complete problems

It means no such thing. Postselection is an unphysical resource: to realize it you would have to either reverse a measurement collapse or repeat an experiment until an event of probability as small as $2^{-n}$ finally fires — an exponential cost either way. The theorem characterizes an idealized model, and its value is as a proof tool, not a recipe. Two related traps. First, postselection is not "repeat until success in reasonable time," nor conditioning on a polynomial-probability event; the defining feature is conditioning on events whose probability may be exponentially small, and that is precisely what lifts $\mathsf{BQP}$ to $\mathsf{PP}$ — a poly-probability postselection buys nothing. Second, the equality is used contrapositively: it lets us argue that if classical machines could simulate quantum sampling, then classical postselection would equal $\mathsf{PP}$ and collapse $\mathsf{PH}$ . The strength of the forbidden model is exactly what makes the hardness conclusion about real classical computers strong.

Worked examples

1 · Renormalization by hand (confidence builder)

A two-qubit register (output $o$ , postselect $p$ ) is left in the state $|\psi\rangle=\sqrt{0.80}\,|o{=}0,p{=}0\rangle+\sqrt{0.15}\,|o{=}1,p{=}0\rangle+\sqrt{0.01}\,|o{=}0,p{=}1\rangle+\sqrt{0.04}\,|o{=}1,p{=}1\rangle$ . Find the postselection probability, the conditional acceptance, and contrast it with the raw acceptance.

Step 1. The four squared amplitudes are the outcome probabilities: $0.80,\,0.15,\,0.01,\,0.04$ , summing to $\mathbf{1.00}$ as required.

Step 2. Postselection probability is the total weight on $p=1$ : $\Pr[p=1]=0.01+0.04=\mathbf{0.05}$ . Only one-twentieth of the wavefunction survives conditioning; in a real $\mathsf{PostBQP}$ circuit this could be as small as $2^{-n}$ .

Step 3. Renormalize the surviving branch via equation (4): $\Pr[o=1\mid p=1]=\dfrac{0.04}{0.01+0.04}=\dfrac{0.04}{0.05}=\mathbf{0.8}\ge\tfrac23$ , so the machine accepts.

Step 4. Contrast with the un-postselected reading: $\Pr[o=1]=0.15+0.04=\mathbf{0.19}$ , which is below one-half and would say reject. Postselection has flipped the verdict by discarding the $p=0$ mass and rescaling the sliver. The rare branch (weight 0.05), once renormalized, accepts with probability 0.8 — even though the raw distribution favours reject.

2 · Encoding a counting threshold in one qubit (fully worked)

Let $n=4$ , so there are $2^n=16$ inputs and the $\mathsf{PP}$ threshold is $2^{n-1}=8$ . For a predicate with count $s=10$ (a yes-instance) and a second with $s=6$ (a no-instance), build the encoded qubit and show the postselected rotation reads off $\mathrm{sgn}(s-8)$ .

Step 1. Encode each count as $|\phi\rangle=\sqrt{\tfrac{16-s}{16}}\,|0\rangle+\sqrt{\tfrac{s}{16}}\,|1\rangle$ . For $s=10$ : $\alpha=\sqrt{6/16}=\mathbf{0.6124}$ , $\beta=\sqrt{10/16}=\mathbf{0.7906}$ . For $s=6$ : $\alpha=0.7906$ , $\beta=0.6124$ — the roles swap.

Step 2. The comparison lives in the ratio $\beta/\alpha=\sqrt{s/(16-s)}$ : for $s=10$ it is $\sqrt{10/6}=\mathbf{1.291}>1$ , and for $s=6$ it is $\sqrt{6/10}=\mathbf{0.775}<1$ . The ratio crosses $1$ exactly at $s=8$ , so its position relative to $1$ is the $\mathsf{PP}$ answer.

Step 3. Apply the real rotation $R_\theta$ with $\theta=-\pi/4$ (a Hadamard-like mix). By equation (7), the amplitude landing on $|1\rangle$ is $\langle1|R_\theta|\phi\rangle=\alpha\sin\theta+\beta\cos\theta=\dfrac{\beta-\alpha}{\sqrt2}$ . For $s=10$ this is $(0.7906-0.6124)/\sqrt2=+\mathbf{0.126}$ ; for $s=6$ it is $-\mathbf{0.126}$ . The difference mode $\beta-\alpha$ has been isolated, and its sign equals $\mathrm{sgn}(s-8)$ .

Step 4. Postselect on the register that keeps this difference mode. Because the surviving amplitude is renormalized, even a one-unit gap in $s$ (say $s=9$ versus $s=7$ ) is inflated to a constant conditional bias past $2/3$ or below $1/3$ — the magnitude of $s-8$ never enters. Reading $o$ returns the verdict. The yes-instance $s=10$ yields a positive difference mode and accepts; the no-instance $s=6$ yields a negative one and rejects — the sign of $s-2^{n-1}$ , amplified to constant bias by postselection.

Physics of the portrait

$\mathsf{PostBQP}=\mathsf{PP}$ is where quantum information theory pays a debt back to classical complexity: an idealized quantum model delivers a two-paragraph proof of a theorem that classical theorists had won only by hard combinatorics. Both the equality and its supremacy applications trace to one person.

Origins · 1 minScott Aaronson and how this was discovered

Scott Aaronson

born 1981, theoretical computer scientist, UT Austin · proved PostBQP = PP and shaped quantum-supremacy theory

Scott Aaronson is among the most influential quantum complexity theorists of his generation, as much for reframing questions as for answering them. He completed his PhD under Umesh Vazirani at Berkeley in 2004, and it was there, as a graduate student, that he discovered the equality $\mathsf{PostBQP}=\mathsf{PP}$ — published in "Quantum Computing, Postselection, and Probabilistic Polynomial-Time" (Proc. R. Soc. A 461, 2005). The result was striking not only for its content but for its economy: the same paper reproves, in a few lines, that $\mathsf{PP}$ is closed under intersection, a fact whose original proof by Beigel, Reingold and Spielman had been a technical landmark. Aaronson turned the model into a tool. With his student Alex Arkhipov he introduced BosonSampling in 2011, using postselection and the $\#\mathsf{P}$ -hardness of the permanent to give the first rigorous argument that a rudimentary quantum device could perform a sampling task no efficient classical computer can match unless the polynomial hierarchy collapses. Alongside the research he built the community's infrastructure — the Complexity Zoo encyclopedia of complexity classes, and the long-running blog Shtetl-Optimized — and now directs the quantum information center at the University of Texas at Austin. The postselection theorem remains his signature: a physically impossible machine, made into a lens that sharpens what we can prove about the possible ones.

History

1977

— Gill formalizes PP, probabilistic polynomial time with an unbounded one-half threshold

1991

— Toda proves PH ⊆ Pᴾᴾ, so the whole polynomial hierarchy reduces to counting

1991

— Beigel, Reingold and Spielman prove PP is closed under intersection

2004

— Aaronson proves PostBQP = PP and reproves the closure result in two paragraphs

2011

— Aaronson–Arkhipov and Bremner–Jozsa–Shepherd build sampling-hardness on the equality

Going further

Texts. Aaronson, "Quantum Computing, Postselection, and Probabilistic Polynomial-Time", Proc. R. Soc. A 461 (2005) 3473 · Nielsen & Chuang, Quantum Computation and Quantum Information, Ch. 4 and the complexity appendix · Watrous, Quantum Computational Complexity (survey) and The Theory of Quantum Information · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, AMS (2002) · Aaronson & Arkhipov, "The Computational Complexity of Linear Optics", Theory of Computing 9 (2013) 143 · Bremner, Jozsa & Shepherd, Proc. R. Soc. A 467 (2011) 459 · Toda, "PP is as hard as the polynomial-time hierarchy", SIAM J. Comput. 20 (1991) 865. Key identities to keep in view: (1) $|a_y|^2$ is $\mathsf{GapP}$ over the $\{H,\text{Toffoli}\}$ gate set, and the ratio-of- $\mathsf{GapP}$ -sums acceptance predicate is a $\mathsf{PP}$ sign test; (2) the single-qubit encoding uses $\alpha=\sqrt{(2^n-s)/2^n}$ , $\beta=\sqrt{s/2^n}$ , giving $\langle1|R_\theta|\phi\rangle=\alpha\sin\theta+\beta\cos\theta$ and $\mathrm{sgn}(\beta-\alpha)=\mathrm{sgn}(s-2^{n-1})$ ; (3) the closure-under-intersection corollary follows via conjoined postselection; (4) the collapse template rests on Toda's $\mathsf{PH}\subseteq\mathsf{P}^{\mathsf{PP}}$ and $\mathsf{PostBPP}\subseteq\Sigma_3^{\mathsf p}$ . The worked numbers ( $\Pr[o=1\mid p=1]=0.04/0.05=0.8$ ; $\beta/\alpha=\sqrt{10/6}=1.291$ ; $(\beta-\alpha)/\sqrt2=0.126$ at $\theta=-\pi/4$ ) are elementary; the thresholds $1/3,2/3$ are conventional and amplifiable.

Prerequisites. The Complexity Class BQP · BQP is Contained in PP and PSPACE · BQP versus P, NP, and PSPACE. Leads to. Quantum Merlin–Arthur (QMA) · QIP = PSPACE · The Polynomial Method for Quantum Lower Bounds.

Ask the tutor: Want the postselected rotation worked out angle by angle for a small count, or to see how the same collapse argument powers the BosonSampling and IQP supremacy proofs?

Is postselection something a real quantum computer can do?

No — and that is the whole point. Postselection means conditioning on a measurement outcome that may have probability as small as $2^{-n}$ , keeping only the branch where the flag qubit read $|1\rangle$ and discarding everything else. To do that physically you would have to either undo a measurement collapse (impossible) or repeat the experiment until the rare outcome happens (exponentially many trials on average). $\mathsf{PostBQP}$ is a theorist's idealization. Its worth is entirely as a proof device: the equality $\mathsf{PostBQP}=\mathsf{PP}$ lets us reason about real classical and quantum machines by routing an argument through an unphysical one, most famously to conclude that efficient classical simulation of quantum sampling would collapse the polynomial hierarchy.

Does PostBQP = PP mean quantum computers can solve PP-complete problems efficiently?

No. The theorem describes the postselecting model, not a physical quantum computer. A genuine $\mathsf{BQP}$ machine has no access to postselection, so it does not inherit $\mathsf{PP}$ 's power — indeed $\mathsf{BQP}$ is believed to be far smaller than $\mathsf{PP}$ and even incomparable to $\mathsf{NP}$ . What the equality does say is that if you could postselect, you could decide any counting problem in $\mathsf{PP}$ ; since you cannot, the statement is a characterization of an idealized resource. Reading it as "quantum computers solve $\mathsf{PP}$ " is the single most common misconception about the result.

Why does an exponentially rare postselection give power, when a likely one would not?

Renormalizing a branch of probability $1/\mathrm{poly}$ only rescales amplitudes by a polynomial factor, which leaves $\mathsf{BQP}$ 's bounded-error structure intact — no new problems become decidable. Conditioning on a branch of probability $2^{-n}$ is different: dividing by that tiny norm can inflate an exponentially small amplitude difference into an order-one state. That difference is often the sign of an exponential ( $\mathsf{GapP}$ ) sum, and detecting the sign of such a sum is the defining ability of $\mathsf{PP}$ . So it is specifically the exponential rarity of the postselected event that carries the extra power; a merely unlikely event is not enough.

What is GapP, and why does it show up here?

$\mathsf{GapP}$ is the class of functions expressible as the difference of two $\#\mathsf{P}$ counting functions — equivalently, the net signed count over an exponential set of paths. It is exactly the shape of a quantum amplitude: over the Hadamard+Toffoli gate set, an amplitude is $(P_y-N_y)/2^m$ , where $P_y$ and $N_y$ count positive- and negative-weight computational paths. $\mathsf{GapP}$ is closed under multiplication, so squaring amplitudes to get probabilities keeps you inside it, and summing over outcomes does too. Since $\mathsf{PP}$ is precisely the class that tests whether a $\mathsf{GapP}$ function is positive, the postselected acceptance condition — a comparison of two $\mathsf{GapP}$ sums — lands squarely in $\mathsf{PP}$ .

How does this give a proof that PP is closed under intersection?

Trivially, on the $\mathsf{PostBQP}$ side. To decide $L_1\cap L_2$ , run the two postselecting machines on disjoint ancillas and postselect on both flag qubits being $|1\rangle$ . Independence makes the joint conditional factor into a product; after amplifying each machine's acceptance close to $0$ or $1$ , that product behaves as a logical AND, giving a single $\mathsf{PostBQP}$ machine for the intersection. Because $\mathsf{PostBQP}=\mathsf{PP}$ , this machine witnesses $L_1\cap L_2\in\mathsf{PP}$ . The original combinatorial proof by Beigel, Reingold and Spielman was substantial; the quantum route compresses it to a paragraph, a clean example of quantum information exporting a technique back to classical complexity.

What exactly is the sampling-hardness collapse argument?

Suppose a classical polynomial-time algorithm could sample from the output distribution of an arbitrary quantum circuit. Grant that classical sampler the power of postselection — call the resulting class $\mathsf{PostBPP}$ . If the sampler faithfully reproduces the quantum distribution, then classical postselection matches quantum postselection, so $\mathsf{PostBPP}=\mathsf{PostBQP}=\mathsf{PP}$ . But $\mathsf{PostBPP}$ is known to sit inside $\Sigma_3^{\mathsf p}$ , low in the polynomial hierarchy, so this would put $\mathsf{PP}\subseteq\mathsf{PH}$ . By Toda's theorem $\mathsf{PH}\subseteq\mathsf{P}^{\mathsf{PP}}$ , and $\mathsf{PP}\subseteq\mathsf{PH}$ then forces $\mathsf{PH}$ to collapse to a finite level — contrary to universal belief. Hence no such efficient classical sampler exists, which is the rigorous core of BosonSampling and IQP supremacy.

Why is PostBQP considered robust the way PP is?

Its definition is insensitive to the details one might worry about. The bounded-error gap can be any constant, or even $1/2\pm 2^{-\mathrm{poly}}$ , because acceptance is amplifiable; the universal gate set can be any set with algebraic entries, by exact emulation and Solovay–Kitaev; and the postselection success probability can be any nonzero value, since only the conditional statistics matter. Each of these invariances mirrors a corresponding robustness of $\mathsf{PP}$ under reparametrization, which is no coincidence — it is a reflection of the equality $\mathsf{PostBQP}=\mathsf{PP}$ . Robustness under such changes is the signature of a "real" complexity class rather than an artifact of a fragile definition.