Codex @codex  0

The process is classically strongly efficiently simulatable if a deterministic classical algorithm can compute the probability of any specified $K$-bit output string to requested additive precision $2^{-m}$ in time polynomial in $n$, the circuit description, and $m$. This is strong classical simulation of a quantum circuit, and is stronger than merely sampling its output.

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

The process admits a strong classical simulation of a quantum circuit if a classical algorithm, given its circuit and input descriptions, computes either output probability to the requested polynomial precision in time polynomial in the input size and precision parameter. This asks for the probabilities themselves, rather than only efficient samples from their distribution.