CNOT Pauli action

For control $c=1$ and target $t=2$, the controlled-X definition [F3,F4] gives $C\mathrm{\mid }{y}_1,\dots ,y_n⟩=\mathrm{\mid }{y}_1,\dots ,y_t+y_c,\dots ,y_n⟩$. Applying this rule twice gives $C^2=I$; it permutes the ordered orthonormal basis, so $C=C^{\ast }$. On a basis vector, in $C{X}_{c}C$ the right CNOT first changes $y_t$ to $y_t+y_c$, the middle $X_c$ changes $y_c$ to $y_c+1$, and the left CNOT changes the target to $y_t+y_c+(y_c+1)=y_t+1$. Thus $C{X}_{c}C=X_c{X}_t$. In $C{X}_{t}C$, the right CNOT changes the target to $y_t+y_c$, the middle $X_t$ toggles it, and the left CNOT toggles it back by $y_c$, leaving $y_t+1$; hence $C{X}_{t}C=X_t$. The middle $Z_c$ contributes $(-1{)}^{y_c}$ and the two CNOTs restore the bits, giving $C{Z}_{c}C=Z_c$. The middle $Z_t$ contributes $(-1{)}^{y_t+y_c}$, giving $C{Z}_{t}C=Z_c{Z}_t$.

For arbitrary distinct wires $c,t\in \{1,\dots ,n\}$, assign source positions $0,1$ to $c-1,t-1$. This partial assignment is injective; list its remaining source and target positions in increasing order and match them in order to extend it to a permutation $\sigma$. By [F6], $P_{\sigma }$ moves those factors into the first two positions and permutes an orthonormal basis bijectively, so $P_{\sigma }$ is unitary. The operator $P_{\sigma }^{-1}(C_{1\to 2}\otimes I_{\mathrm{r}\mathrm{e}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}})P_{\sigma }$ therefore has the stated basis action, and its Pauli conjugation rules are the first-two-wire rules of step 1.1 with local wire names $1,2$ replaced by $c,t$.

Write $P(k,x,z)$ as its ordered product of all $X$-factor maps followed by all $Z$-factor maps. Conjugation preserves this product order. Using step 2.1, the images of the $X$ factors combine to $X_c^{x_c}{X}_t^{x_t+x_c}$ with all other $X$ exponents unchanged; the images of the $Z$ factors combine to $Z_c^{z_c+z_t}{Z}_t^{z_t}$ with all other $Z$ exponents unchanged. Tensor-map composition in [F5] justifies these factorwise products, and no $X$ factor is moved past a $Z$ factor. Thus no scalar is introduced, $k$ is unchanged, and the stated binary updates follow.