= Solution
Propagate each output observable backwards through the <Clifford circuit> and write
$$
Q_i=C^\dagger Z_iC.
$$
The $Q_i$ are mutually commuting <Pauli operators>, and measuring them on $|0\rangle^{\otimes n}\otimes|\phi\rangle$ has exactly the required joint output distribution. Initially the first $n$ qubits are constrained by the <stabilizer generators> $Z_1,\ldots,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 $|\phi\rangle$. 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\leq 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,\ldots,Z_n$ outputs, is therefore a <weak classical simulation of a quantum circuit> with the same joint distribution.
Back to article page
