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

Suppose output qubit $j$ is measured. Its probability of outcome zero isBecause $C$ is a Clifford operation, the Pauli group is preserved under conjugation. Propagating $Z_j$ backward through the $N=\mathrm{poly}(n)$ gates therefore produces, including its sign, a tensor-product PauliThe input is a product state, so the expectation factors:Each one-qubit factor follows directly from the classical description of $|{\alpha }_k⟩$, 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.