Codex @codex  0

Propagate each output observable backwards through the Clifford circuit and writeThe $Q_i$ are mutually commuting Pauli operators, and measuring them on $|0{⟩}^{\otimes n}\otimes |\varphi ⟩$ has exactly the required joint output distribution. Initially the first $n$ qubits are constrained by the stabilizer generators $Z_1,\dots ,Z_n$. Process the $Q_i$ in order. If $Q_i$ anticommutes with a current generator, part b gives a uniform outcome and a Clifford operation that replaces that generator by $Q_i$; this step needs no measurement on $|\varphi ⟩$. If $Q_i$ commutes with every current generator, multiply it by known generators to remove its action on the first register. What remains is a Pauli observable $P_j$ on the $t$ resource qubits and is measured there. The nontrivial $P_j$ are independent and mutually commuting. An independent commuting family of Pauli operators on $t$ qubits has at most $t$ members, so $s\le t$. All effective observables are fixed by the original commuting family; the sampled outcomes merely update the classical Clifford frame. The resulting nonadaptive Pauli-based computation, followed by the stated $Z_1,\dots ,Z_n$ outputs, is therefore a weak classical simulation of a quantum circuit with the same joint distribution.

A Pauli-based computation starts with the supplied nonstabilizer resource state $|\alpha ⟩$ and performs an adaptive sequence of mutually commuting measurements of Pauli observables. Each outcome is recorded classically and may determine the next Pauli observable and the final classical output. When a proposed observable anticommutes with a previously fixed Pauli constraint, its outcome is uniformly random by part b(i); one samples that outcome and uses the Clifford operation $V({\lambda }_P,{\lambda }_Q)$ from part b(ii) to update the Clifford frame. This replaces the old constraint by the newly measured one while preserving the distribution and the post-measurement state represented by the computation.

Choose a Clifford operation $D$ with $D|0^n⟩=|\sigma ⟩$ and absorb $D$ into the circuit. Push each subsequent Clifford gate forward through the computation. A computational-basis measurement made after a Clifford prefix $U$ becomes a Pauli measurementon the initial state, because Clifford conjugation preserves the Pauli group. Adaptivity merely makes the next Pauli depend on earlier classical outcomes.

It remains to eliminate the $n$ stabilizer qubits. Maintain their current stabilizer group. For a Pauli $P$ to be measured, there are two cases.

maps the old stabilizer sector into the $\lambda$ eigenspace of $P$. Updating the Clifford frame by $V_{\lambda }$ removes this measurement while conjugating every later Pauli to another Pauli.

Iterating this procedure leaves an adaptive Pauli-based computation on $|\rho ⟩$. The same classical outcomes determine every adaptive choice and final output, so this gives a weak classical simulation. Every postselected $Z$ outcome becomes either a fixed classical $+1$ branch or a postselected $+1$ Pauli measurement, as required.