Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 324 / 1 / a

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)$.

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.