Instantaneous Quantum Polynomial-Time (IQP)

Instantaneous Quantum Polynomial-Time — IQP — is a deliberately crippled model of quantum computation, built to answer one sharp question: how little quantum structure does it take to defeat every efficient classical simulator? Strip a circuit down until every gate is diagonal in the Pauli- $X$ basis, $e^{i\theta X_S}$ , so that all gates commute and can be applied at once in any order — there is no "first gate", hence instantaneous. Feed in the all-zeros state, measure in the computational ( $Z$ ) basis, and a Hadamard layer brackets the diagonal part. What is left has no adaptivity, no intermediate measurement, no obvious universality; it looks almost classical. It is not. Grant this feeble model one magic power — postselection, the right to condition for free on a rare outcome — and it leaps to $\mathsf{PostBQP}=\mathsf{PP}$ , the counting class powerful enough to tally NP solutions. A classical algorithm that could sample the IQP output distribution, granted the same postselection, would land only inside a fixed level of the polynomial hierarchy. Set the two against Toda's theorem and something has to give: the hierarchy must collapse to its third level, an event complexity theorists treat as essentially impossible. So no efficient classical sampler exists — unless the theoretical universe rearranges itself. Underneath the complexity is a piece of combinatorics: an IQP output probability is the squared gap of a low-degree Boolean form — a Gauss sum, a weight enumerator of a linear code — a number that is #P-hard to compute exactly, the same difficulty that governs the permanent in Boson Sampling. The device samples from a distribution defined by these hard numbers without ever computing one. That gap between sampling and computing is exactly where quantum advantage lives, and IQP is its cleanest laboratory.

Key takeaways

An IQP circuit is a Hadamard sandwich $U=H^{\otimes n}\,D\,H^{\otimes n}$ around a diagonal phase $D=\exp(i\sum_S\theta_S Z_S)$ ; every generator is $X$ -diagonal, all commute, and the task is to sample $x\sim p(x)=|\langle x|U|0^n\rangle|^2$ .
Plain IQP is believed strictly weaker than $\mathsf{BQP}$ (no adaptivity, no universal gate set), yet its output distribution cannot be sampled classically to multiplicative error in polynomial time unless the polynomial hierarchy collapses to its third level.
The lever is postselection: $\mathsf{post\text{-}IQP}=\mathsf{PostBQP}=\mathsf{PP}$ (Bremner–Jozsa–Shepherd via Aaronson), while a classical sampler would place $\mathsf{PP}$ inside $\Delta_3^{\mathsf{p}}$ — Toda's theorem $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}$ then forces the collapse.
The output probability of $0^n$ is $\mathrm{gap}(f)^2/2^{2n}$ where $f$ is a degree- $\le 3$ Boolean form; computing the gap of a cubic is #P-hard, and this counting core is what a classical sampler cannot fake.
Quadratic (Clifford) phases give gaps $=\pm 2^{n/2}$ — anti-concentrated but poly-time computable by Gottesman–Knill; the jump to hardness is exactly the non-Clifford cubic term.
Proven multiplicative-error hardness is worst-case; the additive/total-variation hardness relevant to noisy hardware needs two further conjectures — average-case #P-hardness and anti-concentration — established for some IQP ensembles but not all, and some instances are classically spoofable.
Key idea: IQP restricts all gates to commute (diagonal in $X$ ), removing adaptivity and apparent universality; yet under postselection it equals $\mathsf{PP}$ , so an efficient classical sampler would collapse the polynomial hierarchy — making IQP sampling a rigorous source of classically intractable quantum behaviour from minimal quantum resources.

Where this lives today

IQP is one of three canonical near-term quantum-advantage proposals, sitting alongside Boson Sampling and random-circuit sampling, and it is arguably the most transparent — its hardness proof is a short chain of textbook theorems rather than a bespoke argument about permanents or Haar-random unitaries. Experimentally its appeal is structural: a shallow Hadamard–phase–Hadamard circuit of commuting gates is comparatively friendly to fixed-frequency superconducting processors and to trapped-ion machines, and the diagonal $X$ -program gives a clean, low-parameter description of the ensemble. The active frontier is verifiable advantage: Shepherd and Bremner's construction hides a secret linear code in the $X$ -program so a keyholder can detect a bias a classical spoofer apparently cannot reproduce — a publicly postable challenge with an efficiently checkable answer. That program is a running battle: cryptanalysis has broken specific challenge families (the 2019–2023 attacks on the original stabilizer-based construction), which in turn sharpens the design of harder ensembles. In parallel, the additive-error theory built for IQP — average-case #P-hardness plus anti-concentration — has become the template every subsequent advantage claim is measured against. IQP remains the setting where the community first learned what a rigorous quantum-advantage argument must contain.

The physical picture

Picture an IQP computation as a single diagonal program written in the $X$ basis. You pick a multiset of $X$ -strings — products $X_S=\bigotimes_{j\in S}X_j$ over subsets of qubits — and attach a phase $\theta_S$ to each. Because all $X$ -strings commute, there is no notion of which gate goes first; the whole computation is one operator applied at once. Quantumness survives for two reasons: you measure in the $Z$ basis, orthogonal to the $X$ diagonal, and the two Hadamard layers convert those $X$ -phases into an interference pattern spread over all $2^n$ computational outcomes. The first figure fixes the anatomy — the Hadamard sandwich, the commuting core, and a concrete two-qubit instance whose numbers you can check by hand.

Figure

The IQP anatomy: U = H⊗ⁿ D H⊗ⁿ with a commuting X-diagonal core, input ∣0ⁿ⟩, output measured in Z. The two-qubit instance D = CZ gives amplitude ⟨00∣U∣00⟩ = gap/2ⁿ = 2/4 = 1/2, so p(00) = 1/4

The hardness has a leverage flavour. IQP by itself is plausibly weak — likely a strict subset of $\mathsf{BQP}$ , since it cannot even branch on a measured bit. But grant it one free gift, postselection, and it does not merely improve — it jumps all the way to $\mathsf{PP}$ , the class that decides whether an exponential signed sum is positive. A classical sampler granted the identical gift climbs only to a finite rung, $\Delta_3^{\mathsf p}$ , of the hierarchy. Two objects forced to be equal sit at heights the theory insists are different; the contradiction is the proof. The second figure lays out that lever end to end: the postselection equality on the left, the classical sampler's ceiling on the right, and Toda's theorem as the fulcrum that pries the hierarchy down onto its third level.

Figure

The hardness lever. Left: postselect IQP to reach post-IQP = PostBQP = PP. Right: a classical multiplicative sampler, postselected and counted by Stockmeyer, sits in Δ₃ᵖ. Toda's theorem PH ⊆ P^#P ⊆ P^PP then forces PH ⊆ Δ₃ᵖ — collapse to the third level

Finally, hold the output probability $p(x)$ up to the light and it turns into a number-theoretic object: a Gauss sum, or the weight enumerator of a binary linear code evaluated at roots of unity — computing it exactly is #P-hard, the same wall the permanent hits. The transition from this clean worst-case story to the messy world of noisy hardware — from multiplicative to additive error — is like going from a perfect proof to a robust one, and it demands two extra ingredients we develop below.

The core equations

An IQP computation is fixed once you name the phases $\theta_S$ on each $X$ -string. The canonical form writes the whole thing as a diagonal operator conjugated by Hadamards, which is the cleanest way to see both why the gates commute and why the output is nonetheless quantum.

U=H^{\otimes n}\,D\,H^{\otimes n},\qquad D=\exp\!\Big(i\sum_{S}\theta_S\,Z_S\Big) \qquad (1)

where: $H$ — the single-qubit Hadamard, which conjugates $Z$ into $X$ ; $D$ — a diagonal (computational-basis) phase unitary built from commuting $Z$ -strings; $Z_S=\bigotimes_{j\in S}Z_j$ — a Pauli- $Z$ string on the qubit subset $S$ ; $\theta_S$ — a real phase angle assigned to $S$ ; $n$ — the number of qubits. Reading it: $D$ is diagonal in $Z$ and therefore trivially a product of commuting factors, and the Hadamard layers rotate that diagonal into the $X$ basis where the lab-frame gates $e^{i\theta_S X_S}$ live. The object we actually want is not a decision but a sample. IQP is a sampling problem: reproduce, on a classical computer, the distribution a $Z$ -measurement of $U|0^n\rangle$ produces.

p(x)=\big|\langle x|U|0^n\rangle\big|^2,\qquad x\in\{0,1\}^n \qquad (2)

where: $p(x)$ — the probability of reading bitstring $x$ in the $Z$ basis; $|0^n\rangle$ — the all-zeros input; $\langle x|$ — the computational-basis bra for outcome $x$ . Reading it: a classical sampler must output $x$ with (near) this frequency; it need not — and provably in poly time cannot — compute any individual $p(x)$ . Expanding the two Hadamard layers rewrites the amplitude as an exponential sum over the $2^n$ intermediate strings, and this is where the #P structure first becomes visible.

\langle 0^n|U|0^n\rangle=\frac{1}{2^{n}}\sum_{z\in\{0,1\}^n}\exp\!\Big(i\sum_S\theta_S(-1)^{z\cdot \mathbf 1_S}\Big) \qquad (3)

where: $z$ — the summation index over all $2^n$ basis states threaded between the Hadamard layers; $\mathbf 1_S$ — the indicator vector of $S$ , so $z\cdot\mathbf 1_S=\sum_{j\in S}z_j \bmod 2$ ; the prefactor $2^{-n}$ collects the two $2^{-n/2}$ Hadamard normalizations. Reading it: the amplitude is a normalized sum of $2^n$ unit phasors — exactly the shape of a Gauss sum, and for suitable phases it becomes a #P-hard count. Two complexity facts turn that combinatorics into an impossibility theorem. The first is Aaronson's characterization of postselected quantum computation.

\mathsf{PostBQP}=\mathsf{PP} \qquad (4)

where: $\mathsf{PostBQP}$ — $\mathsf{BQP}$ augmented with postselection on measurement outcomes of nonzero probability; $\mathsf{PP}$ — probabilistic polynomial time, the class deciding whether a signed exponential sum is positive. Reading it: postselection is enormously powerful — it lifts bounded-error quantum computation exactly to the counting class $\mathsf{PP}$ . The second is that IQP, weak as it is, loses nothing under postselection — it also reaches $\mathsf{PP}$ .

\mathsf{post\text{-}IQP}=\mathsf{PostBQP}=\mathsf{PP} \qquad (5)

where: $\mathsf{post\text{-}IQP}$ — IQP circuits with postselection on some output qubits. Reading it: the commuting restriction, which makes plain IQP look sub-universal, is entirely undone by postselection — the postselected model is as strong as postselected universal quantum computing. The fulcrum is Toda's theorem, which bounds the entire polynomial hierarchy by a single counting oracle.

\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}} \qquad (6)

where: $\mathsf{PH}=\bigcup_k\Sigma_k^{\mathsf p}$ — the polynomial hierarchy; $\mathsf{P}^{\#\mathsf{P}}$ — polynomial time with a $\#\mathsf{P}$ counting oracle, and since $\mathsf{PP}\subseteq\mathsf{P}^{\#\mathsf{P}}$ , also $\mathsf{PH}\subseteq\mathsf{P}^{\mathsf{PP}}$ . Reading it: every level of the hierarchy — however high — is swallowed by counting, so anything that pins counting low pins all of $\mathsf{PH}$ low. Put together, a classical sampler that reproduces $p(x)$ even to multiplicative error would collapse the hierarchy.

\Pr_x\big[\,|q(x)-p(x)|\le c\,p(x)\,\big]=1\ \Longrightarrow\ \mathsf{PH}=\Sigma_3^{\mathsf p} \qquad (7)

where: $q(x)$ — the probability a hypothetical efficient classical sampler assigns to $x$ ; $c<\sqrt2$ — the multiplicative-error constant the proof tolerates. Reading it: the conclusion " $\mathsf{PH}$ collapses to its third level" is what nobody believes, so the premise "such a sampler exists" is what must be false. Finally, the combinatorial identity that makes the hardness concrete: the all-zeros probability is the squared gap of a Boolean form.

p(0^n)=\frac{\mathrm{gap}(f)^2}{2^{2n}},\qquad \mathrm{gap}(f)=\#\{z:f(z)=0\}-\#\{z:f(z)=1\} \qquad (8)

where: $f$ — a degree- $\le 3$ Boolean form over $\mathbb F_2$ fixed by the diagonal $D$ when $D|z\rangle=(-1)^{f(z)}|z\rangle$ ; $\mathrm{gap}(f)$ — the difference of counts, a $\#\mathsf{P}$ quantity. Reading it: for cubic $f$ the gap is #P-hard to compute exactly, and Derivation B shows this is precisely the number a classical sampler cannot fake.

Derivation AWhy postselected IQP is as strong as postselected universal computation

The goal is to show the single most surprising fact in the subject: that IQP, a model with no adaptivity, no intermediate measurement, and only commuting gates, becomes universal for $\mathsf{PP}$ the instant we allow postselection. We build the two containments that pin $\mathsf{post\text{-}IQP}$ from both sides — the easy direction into $\mathsf{PostBQP}$ , and the hard direction out of it — using postselection to manufacture the very adaptivity and non-commuting structure that plain IQP lacks, then close the loop through Aaronson's theorem.

Step 1. The easy containment $\mathsf{post\text{-}IQP}\subseteq\mathsf{PostBQP}$ is immediate: an IQP circuit is a legal quantum circuit, and postselecting some of its output qubits is a legal $\mathsf{PostBQP}$ operation, so anything post-IQP does is a special case of post-BQP. Why: this fixes the ceiling — post-IQP can be no stronger than postselected universal quantum computing.

Step 2. For the reverse, use gate teleportation. Postselecting a Bell-basis measurement onto a chosen outcome teleports a qubit through an entangled resource while applying a chosen gate as the teleportation by-product — the choice that plain IQP could never make, because it has no adaptivity, is simply postselected into existence. Why: postselection buys, for free, the conditional gate application that adaptivity would otherwise supply.

Step 3. With teleportation gadgets available, assemble a universal set. The gates $\{e^{i\pi Z_S/8},\,H\}$ implemented through postselected ancillas are universal, and crucially each diagonal piece can be written as a commuting $X$ -diagonal generator in the IQP frame — the non-Clifford $\pi/8$ phase supplies the "magic" that lifts the Clifford floor. Why: universality needs one non-Clifford gate plus Clifford operations, and postselected IQP can synthesize exactly that.

Step 4. Therefore $\mathsf{PostBQP}\subseteq\mathsf{post\text{-}IQP}$ ; combined with Step 1 this gives $\mathsf{post\text{-}IQP}=\mathsf{PostBQP}$ , and Aaronson's theorem $\mathsf{PostBQP}=\mathsf{PP}$ closes the chain to $\mathsf{post\text{-}IQP}=\mathsf{PP}$ . Why: sandwiching between the two containments forces equality, and the known value of the middle class hands us $\mathsf{PP}$ . *Verified: each containment is a standard result — gate teleportation (Gottesman–Chuang), universality of Clifford+ $T$ / $e^{i\pi Z/8}$ , and $\mathsf{PostBQP}=\mathsf{PP}$ (Aaronson 2005); the equality $\mathsf{post\text{-}IQP}=\mathsf{PP}$ is Bremner–Jozsa–Shepherd 2011.*

Go deeper · Derivation B · 2 minClassical IQP sampling collapses the polynomial hierarchy

Derivation BClassical IQP sampling collapses the polynomial hierarchy

The goal is the flagship hardness theorem: if any polynomial-time classical randomized algorithm can sample the IQP output distribution to within a constant multiplicative error, then the polynomial hierarchy collapses to its third level — an outcome complexity theory treats as tantamount to a contradiction. We chain the postselection equality of Derivation A with Stockmeyer's approximate-counting theorem and Toda's theorem, tracking exactly which oracle each step costs so the final containment lands cleanly at $\Delta_3^{\mathsf p}$ .

Step 1. Assume a sampler: a classical randomized algorithm outputs $x$ with probability $q(x)$ obeying $|q(x)-p(x)|\le c\,p(x)$ for all $x$ , some constant $c<\sqrt2$ . Multiplicative closeness is the strong notion — it controls even the exponentially small probabilities. Why: this is the object whose existence we will drive to absurdity.

Step 2. Postselect both distributions on the same rare event that defines $\mathsf{post\text{-}IQP}$ . Conditioning preserves multiplicative closeness, so $q(\,\cdot\mid\mathrm{cond})$ still multiplicatively approximates $p(\,\cdot\mid\mathrm{cond})$ — the classical sampler now tracks a postselected quantum computation. Why: this transports the hypothesis into the regime where IQP is maximally powerful.

Step 3. Apply Stockmeyer. Given the classical sampler's polynomial-size description, Stockmeyer's theorem lets an NP oracle multiplicatively estimate the probability the sampler assigns to any event, in particular $\Pr[\mathrm{cond}]$ — placing that estimation in $\mathsf{BPP}^{\mathsf{NP}}\subseteq\Delta_3^{\mathsf p}$ . Why: this is the only place classicality is used — a genuine quantum amplitude has no such efficiently-estimable description, which is exactly the asymmetry the proof exploits.

Step 4. Invoke Derivation A. Since $\mathsf{post\text{-}IQP}=\mathsf{PP}$ , the postselected probability the NP oracle just estimated decides a $\mathsf{PP}$ -complete problem, giving $\mathsf{PP}\subseteq\Delta_3^{\mathsf p}$ . Why: the estimable quantity is not some weak marginal — it carries the full $\mathsf{PP}$ power of postselected IQP.

Step 5. Apply Toda. Toda's theorem gives $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}\subseteq\mathsf{P}^{\mathsf{PP}}$ ; feeding in $\mathsf{PP}\subseteq\Delta_3^{\mathsf p}$ shows $\mathsf{P}^{\mathsf{PP}}\subseteq\Delta_3^{\mathsf p}$ , so every level of $\mathsf{PH}$ is trapped inside $\Delta_3^{\mathsf p}$ — the hierarchy collapses to $\Sigma_3^{\mathsf p}$ . Why: Toda is the amplifier that turns "counting is easy-ish" into "the entire hierarchy is shallow".

Step 6. Conclude by contraposition. The polynomial hierarchy is conjectured to be infinite (non-collapsing), a belief as load-bearing as $\mathsf{P}\neq\mathsf{NP}$ . Since the sampler forces collapse, no such efficient classical multiplicative-error sampler exists — IQP sampling is classically hard. Why: we never prove sampling hard outright; we show it would demolish a pillar of complexity theory, which is the strongest unconditional-looking evidence the field offers. *Verified: every containment is textbook — Aaronson (PostBQP=PP), Stockmeyer (approximate counting, BPP^NP ⊆ Δ₃ᵖ), Toda (PH ⊆ P^#P). The "collapse to the third level" conclusion matches Bremner–Jozsa–Shepherd 2011, Theorem 1.*

Go deeper · Derivation C · 2 minThe output probability as a squared gap and its #P-hard core

Derivation CThe output probability as a squared gap and its #P-hard core

The goal is to make the hardness tangible by computing an IQP probability in closed form and identifying the exact combinatorial quantity that resists classical computation. We specialize the diagonal $D$ to a real sign operator, evaluate the all-zeros amplitude as a normalized character sum, square it to a probability, and then pin the resulting integer — the gap of a Boolean form — to the #P-complete problem of counting solutions of a cubic over $\mathbb F_2$ .

Step 1. Take $D$ real: $D|z\rangle=(-1)^{f(z)}|z\rangle$ for a degree- $\le 3$ Boolean form $f$ , realizable with commuting $Z$ , $CZ$ , and $CCZ$ gates (equivalently $X$ -diagonal in the IQP frame). Then equation (3) collapses to a sign sum, $\langle 0^n|U|0^n\rangle=2^{-n}\sum_z(-1)^{f(z)}$ . Why: real $\pm1$ phases turn the Gauss sum into a plain count, exposing the arithmetic underneath.

Step 2. Split the sum by the value of $f$ . With $N_b=\#\{z:f(z)=b\}$ and $N_0+N_1=2^n$ , the amplitude is $2^{-n}(N_0-N_1)=2^{-n}\,\mathrm{gap}(f)$ . Why: the amplitude is literally the normalized imbalance between the zeros and ones of $f$ — a single #P-flavoured integer.

Step 3. Square to a probability: $p(0^n)=\mathrm{gap}(f)^2/2^{2n}$ . Writing $\mathrm{gap}(f)^2=(N_0-N_1)^2$ and using $N_0+N_1=2^n$ gives the equivalent form $p(0^n)=\tfrac12\big(1+2^{-2n}\,\mathrm{gap}(f)^2\big)-\tfrac12$ — but the compact statement (8) is what we use. Why: the observable probability is fixed entirely by one integer, so simulating the device is at least as hard as producing that integer.

Step 4. Now the punchline. Counting solutions of a general degree-3 polynomial equation over $\mathbb F_2$ is #P-complete, so computing $N_0$ — and hence $\mathrm{gap}(f)$ and $p(0^n)$ — is #P-hard. More generally, for arbitrary phases the amplitude is a normalized Gauss sum equal to a weight-enumerator value of the linear code defined by the $X$ -program's support matrix. Why: this is the counting wall; it is the same complexity that guards the permanent in Boson Sampling.

Step 5. Contrast the tractable case. If $f$ is only quadratic (a Clifford circuit — $Z$ , $CZ$ , $S$ gates), the gap is a classical Gauss sum equal to $0$ or $\pm 2^{n/2}$ and computable in polynomial time by Gottesman–Knill; hardness genuinely requires the cubic ( $CCZ$ , non-Clifford) term. Why: this locates the precise resource — degree-3 phase, i.e. non-Cliffordness — responsible for the leap from easy to #P-hard. *Verified: $|N_0(+1)+N_1(-1)|^2=(N_0-N_1)^2$ (no cross term, since the phases are real); the 2-qubit $CZ$ instance gives $N_0=3,N_1=1,\mathrm{gap}=2,p(00)=4/16=1/4$ , matching a direct amplitude computation; quadratic Gauss sums have modulus $2^{n/2}$ (Weil), giving $p=2^{-n}$ .*

Limiting cases

IQP hardness is not one statement but a lattice of them; which one holds depends on the error model and on which auxiliary conjectures you are willing to grant.

Case	Result	Meaning
Exact / postselected	$\mathsf{post\text{-}IQP}=\mathsf{PostBQP}=\mathsf{PP}$	with postselection IQP attains full $\mathsf{PP}$ power; exact classical sampling is impossible unless $\mathsf{PH}$ collapses to its third level
Multiplicative error	$\vert q(x)-p(x)\vert\le c\,p(x),\ c<\sqrt2$	a sampler with constant multiplicative error still collapses $\mathsf{PH}$ — the rigorously proven IQP hardness regime
Additive / TV error	$\tfrac12\sum_x\vert q(x)-p(x)\vert\le\epsilon$	the regime a noisy device meets; hardness is conjectural, needing average-case #P-hardness plus anti-concentration
Quadratic (Clifford) phases	$\mathrm{gap}=0$ or $\pm 2^{n/2}$ , $p(0^n)=2^{-n}$	anti-concentrated yet poly-time simulable by Gottesman–Knill — non-Clifford cubic term is essential
No postselection, no conjectures	$\mathsf{IQP}\stackrel{?}{\subsetneq}\mathsf{BQP}$	plain IQP is believed strictly weaker than $\mathsf{BQP}$ — it lacks adaptivity and is not known to decide universal quantum problems

Common trapCommuting gates are not classically easy gates

The single most common misreading is "the gates all commute, so the circuit must be classically simulable." Commutation removes temporal structure — there is no gate order to track — but it removes neither entanglement nor interference. The Hadamard sandwich spreads a commuting phase over all $2^n$ outcomes, and the resulting probabilities encode #P-hard gaps. A second, subtler trap: the proven hardness is multiplicative and worst-case, whereas a noisy device achieves only small total-variation error on a typical instance. Bridging that gap needs two unproven conjectures — average-case #P-hardness of typical output probabilities, and anti-concentration so errors cannot hide on a few dominant outcomes. IQP is therefore not unconditionally hard, and specific engineered ensembles have been classically spoofed. "Commuting" buys simplicity of description, not classical tractability — and "hard in the worst case" is not yet "hard for the chip on the bench".

Worked examples

1 · A two-qubit IQP circuit, worked end to end (confidence builder)

Take $n=2$ and the single diagonal gate $D=CZ$ , so $D|z\rangle=(-1)^{z_1 z_2}|z\rangle$ . Compute the amplitude $\langle 00|U|00\rangle$ and the probability $p(00)$ two ways — by the gap formula and by direct evolution — and check they agree.

Step 1. Gap route. The Boolean form is the quadratic $f(z)=z_1 z_2$ . It vanishes unless both bits are $1$ , so $N_0=\#\{00,01,10\}=3$ and $N_1=\#\{11\}=1$ . The gap is $\mathrm{gap}(f)=N_0-N_1=3-1=\mathbf{2}$ .

Step 2. Amplitude and probability from (8): $\langle 00|U|00\rangle=\mathrm{gap}(f)/2^{n}=2/4=\mathbf{1/2}$ , hence $p(00)=\mathrm{gap}(f)^2/2^{2n}=4/16=\mathbf{1/4}$ .

Step 3. Direct check. Evolve explicitly. First Hadamard layer: $H^{\otimes 2}|00\rangle=\tfrac12(|00\rangle+|01\rangle+|10\rangle+|11\rangle)$ . Apply $CZ$ , flipping the sign of $|11\rangle$ : $\tfrac12(|00\rangle+|01\rangle+|10\rangle-|11\rangle)$ . Overlap with the second layer, $\langle 00|H^{\otimes 2}=\tfrac12(\langle 00|+\langle 01|+\langle 10|+\langle 11|)$ : the inner product is $\tfrac12\cdot\tfrac12\,(1+1+1-1)=\tfrac14\cdot 2=\mathbf{1/2}$ . Squaring gives $p(00)=\mathbf{1/4}$ , matching Step 2 exactly.

Step 4. Read the lesson. A single $CZ$ is a Clifford (quadratic) gate, so this instance is trivially classical — as it must be, since $2$ qubits can never be hard. But the machinery — gap, amplitude, probability — is identical to the hard case; only the degree of $f$ changes. The circuit gives $p(00)=1/4$ , and the gap formula reproduces the direct amplitude to the digit.

2 · Why hardness needs a cubic: Clifford anti-concentration versus #P

Compare an IQP circuit whose phase form $f$ is a nondegenerate quadratic (Clifford) with one whose $f$ contains a cubic term (non-Clifford). Show the quadratic case is anti-concentrated yet efficiently computable, and that hardness enters only with the cubic.

Step 1. Quadratic case. For a nondegenerate quadratic form $Q$ over $\mathbb F_2^n$ , the character sum is a Gauss sum with $\sum_z(-1)^{Q(z)}=\pm 2^{n/2}$ , so $\mathrm{gap}=\pm 2^{n/2}$ and $p(0^n)=(2^{n/2})^2/2^{2n}=2^n/2^{2n}=\mathbf{2^{-n}}$ . The all-zeros probability sits exactly at the uniform value — the distribution is anti-concentrated, spread across outcomes rather than piled on a few.

Step 2. Yet it is easy. A quadratic phase circuit is Clifford, so by Gottesman–Knill the entire output distribution is sampled — and each probability computed — in polynomial time. Anti-concentration alone therefore does not imply hardness; the two properties are independent. Anti-concentrated but classically trivial.

Step 3. Cubic case. Add one $CCZ$ , making $f$ degree $3$ . Now $\mathrm{gap}(f)$ is the solution count of a cubic over $\mathbb F_2$ , a #P-complete quantity; no polynomial-time formula for $p(0^n)$ is known or expected. The distribution can still be anti-concentrated, but now the individual probabilities are genuinely hard.

Step 4. The moral for advantage. A convincing quantum-advantage ensemble needs both anti-concentration (so a noisy sample stays informative) and average-case #P-hardness (so no classical shortcut exists) — and only the non-Clifford degree-3 structure supplies the second. The jump from $\mathsf{P}$ to #P-hard is exactly the jump from quadratic to cubic phase — the single non-Clifford resource that makes IQP interesting.

Physics of the portrait

IQP is where the abstract machinery of counting complexity meets a buildable chip. Its story runs from a 1991 counting theorem, through a 2005 insight about postselection, to a 2009 model and a 2011 collapse theorem — and on to the noisy-device frontier that occupies the field today.

Origins · 1 mininstantaneous quantum polynomial-time and how this was discovered

instantaneous quantum polynomial-time

commuting X-diagonal circuits, Shepherd–Bremner 2009 · quantum computational advantage from minimal resources

The idea of Instantaneous Quantum Polynomial-Time was introduced by Dan Shepherd and Michael Bremner in 2009, in a paper whose title — "Temporally unstructured quantum computation" — names its defining feature: a circuit with no gate order at all. Their motive was not to build a better quantum computer but a worse one, stripped to the bone, to isolate the minimal quantum ingredient that still defeats classical simulation. The model stood on two older pillars. Seinosuke Toda's 1991 theorem, $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}$ , had shown that counting sits above the entire polynomial hierarchy; and Scott Aaronson's 2005 result, $\mathsf{PostBQP}=\mathsf{PP}$ , had revealed postselection as a bridge from quantum amplitudes to counting. In 2011 Bremner, Richard Jozsa, and Shepherd combined these into the flagship theorem: an efficient classical sampler for commuting quantum circuits would collapse $\mathsf{PH}$ to its third level. Shepherd and Bremner had already turned the code-theoretic structure of IQP output into a cryptographic challenge — a distribution whose hidden bias a keyholder can verify while the sampling itself looks hard — the first blueprint for verifiable quantum advantage. The 2016 sequel by Bremner, Ashley Montanaro, and Shepherd pushed the hardness from exact to approximate sampling by proving average-case #P-hardness and anti-concentration for natural IQP ensembles, the template later imitated for random-circuit sampling. IQP thus began as a thought experiment about how little quantum is enough and became one of the best-understood routes to computational quantum advantage.

History

1991

— Toda proves PH ⊆ P^#P, placing counting above the whole hierarchy

2005

— Aaronson shows PostBQP = PP, making postselection a bridge to counting

2009

— Shepherd and Bremner introduce IQP and the hidden-code verification challenge

2011

— Bremner, Jozsa and Shepherd prove classical IQP sampling collapses PH

2016

— Bremner, Montanaro and Shepherd establish average-case hardness and anti-concentration

Going further

Texts and papers. Shepherd & Bremner, "Temporally unstructured quantum computation", Proc. R. Soc. A 465, 1413 (2009) · Bremner, Jozsa & Shepherd, "Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy", Proc. R. Soc. A 467, 459 (2011) · Bremner, Montanaro & Shepherd, "Average-case complexity versus approximate simulation of commuting quantum computations", Phys. Rev. Lett. 117, 080501 (2016) · Aaronson, "Quantum computing, postselection, and probabilistic polynomial-time", Proc. R. Soc. A 461, 3473 (2005) · Toda, "PP is as hard as the polynomial-time hierarchy", SIAM J. Comput. 20, 865 (1991) · Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniv. ed., Ch. 4 · Preskill, Lecture Notes on Quantum Computation, quantum-complexity chapter · Watrous, The Theory of Quantum Information.

Provenance. A verifier should reconstruct: (1) the Hadamard conjugation $HZH=X$ and the resulting $X$ -diagonal commuting form, and the amplitude expansion (3) into a normalized character sum (Nielsen–Chuang Ch. 4; Bremner–Jozsa–Shepherd 2011); (2) the gap identity (8) and the 2-qubit $CZ$ check $\mathrm{gap}=2$ , $p(00)=1/4$ , together with the Clifford Gauss-sum value $|\mathrm{gap}|=2^{n/2}$ ; (3) the containment chain $\mathsf{post\text{-}IQP}=\mathsf{PostBQP}=\mathsf{PP}$ (Aaronson 2005), Stockmeyer approximate counting in $\mathsf{BPP}^{\mathsf{NP}}\subseteq\Delta_3^{\mathsf p}$ , and Toda $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}$ , yielding collapse to the third level under multiplicative-error sampling. Standard complexity facts ( $\mathsf{PP}$ , $\mathsf{PH}$ , $\Delta_3^{\mathsf p}$ , $\mathsf{BPP}^{\mathsf{NP}}$ ) follow Arora–Barak; all "numbers" here are structural (levels of $\mathsf{PH}$ , class equalities, small exact gaps) — no empirical constants are fabricated.

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

Ask the tutor: Ask me to walk through the postselection-to-collapse chain line by line, or to build a small IQP instance and compute its output gap by hand.

Is IQP a real quantum computer, or just a theoretical toy?

Both, deliberately. IQP was designed as a sub-universal model — it cannot run Shor's algorithm or anything needing adaptivity, so it is not a general-purpose quantum computer. Its point is the opposite: by removing as much quantum structure as possible while keeping classical simulation hard, it isolates the minimal resource responsible for advantage. But the circuits are entirely buildable — shallow, commuting, and hardware-friendly — which is why IQP is a live experimental proposal for demonstrating quantum advantage, not merely a blackboard object. The toy and the machine are the same thing seen from two directions.

If all the gates commute, why can't I just simulate them classically?

Because commutation removes time ordering, not entanglement or interference. A classical simulator does not get stuck on the order of gates — it gets stuck on the sum over $2^n$ interfering paths that the Hadamard layers create. That sum is a Gauss sum whose value is the gap of a Boolean form, and computing it is #P-hard. Concretely, a diagonal circuit of $CCZ$ gates is fully commuting yet its all-zeros amplitude counts solutions of a cubic over $\mathbb F_2$ — a #P-complete problem. "Commuting" simplifies the description of the circuit, not the simulation of its output.

What exactly is postselection, and why is it so powerful?

Postselection is the fictional ability to condition on a measurement outcome for free, no matter how rare — you run the circuit and simply declare the ancilla came out the way you wanted, keeping those runs at no cost. Real devices cannot do this (rare events cost exponentially many repetitions), which is why $\mathsf{PostBQP}$ is not a claim about buildable machines. Its power is that conditioning on an exponentially unlikely event amplifies a tiny amplitude difference into a decision — exactly what deciding the sign of an exponential sum, the class $\mathsf{PP}$ , requires. In the IQP proof postselection is a tool of the argument, applied equally to the quantum device and to the hypothetical classical sampler, so both are measured on the same powerful yardstick.

Why does the hardness only give "collapse of the polynomial hierarchy" rather than an unconditional proof?

Because an unconditional proof would settle questions like $\mathsf{P}$ versus $\mathsf{NP}$ , which are open. What complexity theory can deliver is conditional impossibility: "if a fast classical IQP sampler existed, then $\mathsf{PH}$ would collapse to its third level." Non-collapse of $\mathsf{PH}$ is one of the field's bedrock conjectures — believed at least as firmly as $\mathsf{P}\neq\mathsf{NP}$ , which is itself a special case. So while not a theorem in the absolute sense, "no fast classical sampler unless $\mathsf{PH}$ collapses" is about the strongest evidence the current theory can provide, and far stronger than the heuristic hardness claims behind most cryptography.

What is the difference between multiplicative-error and additive-error hardness?

Multiplicative error means the classical sampler's probability $q(x)$ stays within a constant factor of $p(x)$ for every outcome, including exponentially unlikely ones — a very demanding requirement, and the regime where IQP hardness is proven. Additive (total-variation) error means the sampled distribution is merely close on average, $\tfrac12\sum_x|q(x)-p(x)|\le\epsilon$ — which is all a noisy device achieves, and all a realistic classical spoofer needs to fake. Hardness in the additive regime is not proven; it requires two extra conjectures — that computing typical probabilities is #P-hard (average-case), and that the distribution is anti-concentrated so error cannot hide on a few outcomes. Closing this gap is the central technical program of the field.

Where does coding theory enter, and why does it matter for verification?

The support sets $S$ of an IQP $X$ -program form the rows of a matrix over $\mathbb F_2$ — the generator matrix of a binary linear code. The output amplitudes turn out to be weight-enumerator values of that code evaluated at roots of unity, which is why exact computation is #P-hard (weight enumerators are). Shepherd and Bremner exploited this in reverse: by hiding a secret codeword structure, they built an output distribution with a subtle bias only a keyholder can detect, giving a verifiable advantage challenge — a distribution that looks hard to sample yet has an efficiently checkable signature. The catch is that some code constructions leak enough structure to be spoofed classically, so designing secure challenge codes is an ongoing cryptographic arms race.

How does IQP compare to Boson Sampling and random-circuit sampling?

All three are sub-universal sampling proposals sharing one logical skeleton: an output probability equals a #P-hard quantity (a permanent for Boson Sampling, a gap or Gauss sum for IQP, an amplitude for a random circuit), and exact classical sampling would collapse $\mathsf{PH}$ . IQP's distinctive virtue is transparency — its hardness is a short chain of standard theorems, its circuits are the simplest to describe, and it was the first with average-case hardness and anti-concentration proven for natural ensembles. Boson Sampling ties advantage to linear optics and the permanent; random-circuit sampling (the 2019 superconducting experiments) is closest to hardware but has the thinnest average-case guarantees. IQP is the theoretical anchor of the trio.