= Solution
Store a tensor-product element of the <Pauli group> as
$$
P=i^s\bigotimes_{j=1}^nX^{a_j}Z^{b_j},\qquad s\in\mathbb Z/4\mathbb Z,\quad a_j,b_j\in\{0,1\}.
$$
The 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^\dagger P U$ in the question, direct multiplication of the two-by-two matrices gives
$$
H^\dagger XH=Z,\quad H^\dagger ZH=X,\quad H^\dagger XZH=-XZ,
$$
and
$$
S^\dagger XS=-iXZ,\quad S^\dagger ZS=Z,\quad S^\dagger XZS=-iX.
$$
These <backward Pauli updates for Hadamard and phase gates> use $S^\dagger P S$, not $SPS^\dagger$. On the affected line $j$, the updates are
$$
\begin{aligned}
H_j:&\quad(a_j,b_j)\mapsto(b_j,a_j),\quad s\mapsto s+2a_jb_j,\\
S_j:&\quad(a_j,b_j)\mapsto(a_j,b_j\oplus a_j),\quad s\mapsto s-a_j.
\end{aligned}
$$
All phases are reduced modulo four and the updates use the old bits.
For a <Controlled-Z gate> on lines $j,k$, its diagonal action gives
$$
CZ\,X_j\,CZ=X_jZ_k,\quad CZ\,X_k\,CZ=Z_jX_k,\quad
CZ\,Z_j\,CZ=Z_j,\quad CZ\,Z_k\,CZ=Z_k.
$$
For 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 is
$$
\boxed{b_j\mapsto b_j\oplus a_k,\quad b_k\mapsto b_k\oplus a_j,\quad
s\mapsto s+2a_ja_k,\quad a_j,a_k\text{ unchanged}.}
$$
The phase arises when a newly introduced $Z_k$ is moved past $X_k$. For instance $X_jX_k$ becomes $-X_jZ_jX_kZ_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 $\pm1,\pm i$. \b[The classical cost is polynomial], despite the exponentially large matrix of the operation on the full state space.
Back to article page
