Exact output sampling from projected quantum gaps #2102

Prove that the exact quantum probability simulator also yields a classical sampler for the entire joint output distribution, with the same gate-count time bound and polynomial space.

Status: available for implementation. Requested by Samuel. Build on merged #2072 and the projected-probability interface under development in #2094; coordinate changes to that interface with its owner. Related quantum track: #896.

Target

Given an explicitly described, well-formed circuit over Hadamard, NOT, CNOT and Toffoli gates and an explicit computational-basis input register, let:

• $L$ be the number of gates and $h$ the number of Hadamards;
• $N$ be the total encoded length of the gate list and the explicit input register, including the width/output-length cost.

Construct a uniform $h$-bit seed followed by a deterministic decoder whose output law equals the circuit's existing final computational-basis measurement PMF. Certify, for every seed,

$$ \text{time}\le \operatorname{poly}(N), 2^{O((L+1)/\sqrt{\log(L+2)})}, \qquad \text{space}\le \operatorname{poly}(N). $$

The intended randomness guarantee is exactly $h$ sampled fair bits in this seed-decoder formulation; distinguish them from unused transition coins if the native machine model introduces those. Handle $L=0$ and $h=0$.

Proof approach

Use a fixed order on the output wires touched by gates. For a prefix $p$ on those wires, obtain the exact integer mass

$$ M(p)=2^h\Pr[\text{the measured touched wires extend }p]. $$

Prove $M(\varnothing)=2^h$, $M(p)=M(p0)+M(p1)$, and nonnegativity. Draw a uniform rank $u<2^h$. At prefix $p$, compute $M(p0)$: append zero when $u<M(p0)$; otherwise append one and replace $u$ by $u-M(p0)$.

Maintain $0\le u<M(p)$, so zero-mass prefixes are never reached. First prove a reusable deterministic decoding lemma: the number of initial ranks producing each leaf is its integer mass. Instantiate it with the quantum masses to obtain equality of the full joint distributions.

For the quantitative argument:

• At most $3L$ wires are touched. Insert all untouched output bits deterministically from the input register.
• Express arbitrary zero/one prefix events using Quantum time classes NQTIME, EQTIME and PostBQTIME in DTIME[2^O(T/√log T)] by exact gap contraction #2094's projected probabilities; terminal NOT gates on the prefix-zero wires preserve the Hadamard count.
• Each query therefore has $O(L)$ gates, and there are $O(L)$ queries. Sequential contractions reuse polynomial workspace and preserve the exponential factor.
• Encode ranks and masses in binary. Include prefix construction, integer arithmetic, decoding and output writing in the machine bound.

This construction uses integer interval decoding with no rejection loop.

Completion

• Exact projected-prefix masses and their partition identities, reusing the shared quantum definitions.
• A general rank-decoder theorem with exact preimage cardinalities.
• Equality with the existing quantum measurement PMF for the complete output register.
• A native implementation/resource certificate for the seed and decoder, establishing worst-case time and simultaneous polynomial space.
• Meaningful checked examples: a Hadamard, a Bell pair, two successive Hadamards (destructive interference), no gates, and a register with many untouched wires.
• Documentation of the model, encoding, randomness guarantee and attribution; normal repository validation and independent correctness/API review before integration.

This issue concerns computational-basis inputs and final computational-basis measurement in the current gate set. Clifford+T, adaptive measurements and broader time-uniform families are separate follow-ups.

The counting/contraction engine is inherited from #2072, which attributes it to [OpenAI2026ETH], Theorem D.1. This issue proposes a formal sampling consequence and makes no priority claim.

Assisted by ChatGPT.