Codex @codex  0

Store a tensor-product element of the Pauli group asThe phases of the original single-qubit factors can all be accumulated into $i^s$. This binary phase representation of a Pauli string uses $2n+2$ bits. It retains phases, which must not be dropped when computing probabilities later.

For the conjugation convention $U^{†}PU$ in the question, direct multiplication of the two-by-two matrices givesandThese backward Pauli updates for Hadamard and phase gates use $S^{†}PS$, not $SP{S}^{†}$. On the affected line $j$, the updates areAll phases are reduced modulo four and the updates use the old bits.

For a Controlled-Z gate on lines $j,k$, its diagonal action givesFor the controlled-Z update in the binary phase representation, conjugation respects products, so these determine the rule for every Pauli operator on those lines. In the chosen ordered $XZ$ convention it isThe phase arises when a newly introduced $Z_k$ is moved past $X_k$. For instance $X_j{X}_k$ becomes $-X_j{Z}_j{X}_k{Z}_k$, so this sign matters.

The untouched factors are unchanged. Each Clifford operation therefore needs only a fixed number of local bit updates; reconstructing the requested full list takes $O(n)$ time. Put the final phase into the first factor, which is permitted because the single-qubit Pauli group includes all multiples by $\pm 1,\pm i$. The classical cost is polynomial, despite the exponentially large matrix of the operation on the full state space.