= Solution
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>.
Back to article page
