Codex @codex  0

For the first output qubit,A Clifford circuit maps the Pauli observable $Z_1$ under conjugation to a tensor-product Pauli operator $\pm P_1\otimes \cdots \otimes P_n$, found by propagating it backward through the circuit in polynomial time. Since the input is a product state,Each factor is efficiently computable, so both one-bit output probabilities are strongly simulatable. This is Heisenberg propagation of a Pauli observable through a Clifford circuit.

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.

The Gottesman--Knill theorem states that stabilizer-state preparation, Clifford circuits, and adaptive measurements of Pauli observables can be simulated in classical polynomial time. For $|{\Psi }_{\mathrm{in}}⟩=|+{⟩}^{\otimes 3}$, choose generators $XII$, $IXI$, and $IIX$. With each row written as $[x_1{x}_2{x}_3\mid z_1{z}_2{z}_3]$, its sign-free stabilizer tableau isConjugating these generators successively by ${\mathrm{CNOT}}_{21}$, $H_2\otimes H_3$, and ${\mathrm{CNOT}}_{13}$ gives $XIX$, $XZX$, and $ZIZ$. Hence the output tableau, again ignoring signs, is

A strong classical simulation of a quantum circuit computes any requested output probabilityin polynomial time, to the prescribed inverse-polynomial accuracy. A weak classical simulation of a quantum circuit instead produces classical samples from the circuit's output distribution, with exact or suitably small total-variation error.

The Extended Gottesman--Knill theorem states that a unitary Clifford circuit with an arbitrary product state input and final computational-basis measurements is weakly classically simulable. It is strongly simulable when only $O(\log n)$ output qubits are measured. Indeed, each joint output projector expands into $2^k$ Pauli operators, and Clifford conjugation maps every such operator to another Pauli operator whose expectation factors over the input qubits. The factor $2^k$ is polynomial precisely for $k=O(\log n)$.

Stabilizer-state preparation starts from a computational-basis state and applies a Clifford circuit, producing a stabilizer state.