= Solution
A <strong classical simulation of a quantum circuit> computes any requested output probability
$$
p(y)=\Pr(Y=y),\qquad y\in\{0,1\}^k,
$$
in <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)$.
Back to article page
