# Conjugating pairs of Paulis to each other with a Clifford

Let $$A,B$$ be two Paulis with the same order, and neither of which is a multiple of the identity. Then there always exists some Clifford $$C$$ such that $$CAC^\dagger=B$$

Let $$A_1,A_2$$ be two Paulis which anticommute and square to the identity. Let $$B_1,B_2$$ be another pair of Paulis that anticommute and both square to the identity.

Does there always exist some Clifford gate $$C$$ such that simultaneously $$CA_1C^\dagger=B_1 \\ \\ CA_2C^\dagger=B_2$$

Yes. An example of a circuit that does it is a generalized swap. To exchange the encoded qubit $$A$$ defined by logical observables $$A_X = A_1, A_Z = A_2$$ for encoded qubit $$B$$ defined by logical observables $$B_X = B_1, B_Z = B_2$$ you need to perform the encoded cnot sequence
$$C = \text{SWAP}_{A,B} = \text{CNOT}_{A \rightarrow B} \cdot \text{CNOT}_{B \rightarrow A} \cdot \text{CNOT}_{A \rightarrow B}$$
Here is a way to decompose the generalized CNOT gates into one and two qubit gates. Let $$P$$ and $$Q$$ be commuting Pauli products, such as $$P=A_X$$ and $$Q=B_Z$$. Let $$r$$ be one of the qubits involved in $$P$$. From your question, it's clear you know how to find an operation $$M_{P \rightarrow Z_r}$$ that conjugates $$P$$ into a single qubit observable $$Z_r$$. Note that applying this mapping will change $$Q$$ into $$Q^\prime = M_{P \rightarrow Z_r}^\dagger \cdot Q \cdot M_{P \rightarrow Z_r}$$. However, we know $$Q^\prime$$ must commute with $$Z_r$$ because $$Q$$ commuted with $$P$$ and the mapping preserves commutation. From this we know that $$Q^\prime$$ cannot have a term $$X_r$$ or $$Y_r$$, though it may have $$Z_r$$. This allows us to apply the desired CNOT effect by simply iterating over the terms of $$Q^\prime$$ controlling them by $$r$$:
$$\text{CNOT}_{P \rightarrow Q} = M_{P \rightarrow Z_r}^\dagger \cdot \left( \prod_{t \in M_{P \rightarrow Z_r}^\dagger \cdot Q \cdot M_{P \rightarrow Z_r}} \text{Control}(Z_r, t) \right) \cdot M_{P \rightarrow Z_r}$$
where $$\text{Control}(Z_r, Z_r)$$ is just $$Z_r$$ and otherwise $$\text{Control}(Z_r, t)$$ is either a CX, CY, or CZ depending on if $$t$$ is a single-qubit X observable, single-qubit Y observable, or single-qubit Z observable.
Note that a full swap is slightly more specific than what you asked for. You wanted $$A \rightarrow B$$ but I also gave you $$B \rightarrow A$$. If you only want the former, you can achieve it with two generalized CNOTs instead of three.