= Solution
For the first output qubit,
$$
\Pr(0)=\frac12\left[1+
\langle\psi_0|C^\dagger Z_1C|\psi_0\rangle\right].
$$
A <Clifford circuit> maps the Pauli observable $Z_1$ under conjugation to a tensor-product Pauli operator $\pm P_1\otimes\cdots\otimes P_n$, found by propagating it backward through the circuit in polynomial time. Since the input is a product state,
$$
\langle\psi_0|C^\dagger Z_1C|\psi_0\rangle
=\pm\prod_j\langle\alpha_j|P_j|\alpha_j\rangle.
$$
Each factor is efficiently computable, so both one-bit output probabilities are strongly simulatable. This is <Heisenberg propagation of a Pauli observable through a Clifford circuit>.
Back to article page
