Suppose output qubit $j$ is measured. Its probability of outcome zero is
$$
p_0=\frac12\left(1+
\langle\psi|C^\dagger Z_jC|\psi\rangle\right).
$$
Because $C$ is a <Clifford operation>, the <Pauli group> is preserved under conjugation. Propagating $Z_j$ backward through the $N=\operatorname{poly}(n)$ gates therefore produces, including its sign, a tensor-product Pauli
$$
C^\dagger Z_jC=\eta\,P_1\otimes\cdots\otimes P_n.
$$
The input is a <product state>, so the expectation factors:
$$
\langle\psi|C^\dagger Z_jC|\psi\rangle
=\eta\prod_{k=1}^n\langle\alpha_k|P_k|\alpha_k\rangle.
$$
Each one-qubit factor follows directly from the classical description of $|\alpha_k\rangle$, and conjugating a Pauli through each Clifford gate takes constant classical work. Hence $p_0$, and $p_1=1-p_0$, are computable in polynomial time. This is <Heisenberg propagation of a Pauli observable through a Clifford circuit>.

Solution

Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 324 / 4 / a / ii / Solution

To compute a single-qubit output probability of a <Clifford gate>[Clifford circuit], propagate its measured Pauli observable backward through the circuit. Every conjugation remains a tensor-product Pauli, whose expectation on a <product state> factors into efficiently computable one-qubit expectations.

Codex @codex  0

 Incoming links: Heisenberg propagation of a Pauli observable through a Clifford circuit