Are these equivalence relations for the Permutation group equivalent?

Question

Definitions

• $\mathcal{C}$ is the $n$-qubit Clifford group.
• $\mathcal{P}_C$ is the group of $n$-qubit permutation matrices in the $n$-qubit Clifford group. This group is generated by all CNOTs and Pauli $X$ strings. Note that for all $n$, $\mathcal{P}_C$ is a strict subgroup of $\mathcal{C}$.
• $\mathcal{P}$ is the group of all $n$-qubit unitary permutation matrices. There are $2^n!$ such binary unitary matrices. Note that when $n\ge 3$ this group contains many non-Clifford elements. And so for $n \ge 3$, $\mathcal{P}_C$ is a strict subgroup of $\mathcal{P}$

Equivalence relation 1: $P_1 \equiv_1 P_2$ iff $P_1 = Q_L P_2 Q_R$ for some $Q_L,Q_R \in \mathcal{P}_C$. Here $P_1,P_2 \in \mathcal{P}$.

Equivalence relation 2: $P_1 \equiv_2 P_2$ iff $P_1 = C_L P_2 C_R$ for some $C_L,C_R \in \mathcal{C}$. Here $P_1,P_2 \in \mathcal{P}$.

Question

Are these equivalence relations equivalent?

Since $\mathcal{P}_C \subset \mathcal{C}$, $P_1 \equiv_1 P_2 \implies P_1 \equiv_2 P_2$. So the question boils down to does $P_1 \equiv_2 P_2 \implies P_1 \equiv_1 P_2$?

Answer 1

Here is a partial answer based on the suggestion by @unknown.

I'll introduce an intermediate equivalence relation:

Equivalence relation 1.5: $P_1 \equiv_{1.5} P_2$ iff $P_1 = G_L P_2 G_R$ for some $G_L,G_R \in \mathcal{G}_C$.

Here $P_1,P_2 \in \mathcal{P}$ as before and $G_L,G_R$ are generalized permutations (or monomial matrices) in the Clifford group. This group is generated by $\mathcal{G}_C = \mathcal{P}_C \cup \mathcal{D}_C$. $\mathcal{D}_C$ is the diagonal Clifford group. $\mathcal{G}_C$ is a strict subgroup of the Clifford group since no Hadamard gates are contained in the group.

As before, since Since $\mathcal{P}_C \subset \mathcal{G}_C \subset \mathcal{C}$, it must be the case that $P_1 \equiv_1 P_2 \implies P_1 \equiv_{1.5} P_2 \implies P_1 \equiv_2 P_2$.

Now, we will look at the conditions for $G_L P_1 G_R \in \mathcal{P}$. This is a necessary condition for any $P_1 \equiv_{1.5} P_2$.

First, note that any element of $G\in\mathcal{G}_C$ can be written as a product $AD$ where $A\in \mathcal{P}_C$ and $D$ is a diagonal Clifford gate. This is also true for generalized permutations with the full permutation group and any diagonal matrix group. Then, $$G_L P_1 G_R = A_L D_L P_1 A_R D_R = A_L P_1 (P_1^{-1} D_L P_1) A_R D_R = [A_L P_1 A_R] [A_R^{-1} P_1^{-1} D_L P_1 A_R D_R].$$

Since a diagonal matrix conjugated by a permutation matrix is always a diagonal matrix we see that the terms in the first square bracket are all permutations and therefore the product is a permutation. And since $A_R^{-1} P_1^{-1} D_L P_1 A_R$ is a diagonal matrix, we see that the product of all terms in the second square bracket is a diagonal matrix. For $G_L P_1 G_R$ to be a permutation, the diagonal part must be Identity since this is the only element in the union of diagonal gates and permutations.

So, $A_R^{-1} P_1^{-1} D_L P_1 A_R D_R = I \implies D_R = A_R^{-1} P_1^{-1}D_L^{-1} P_1 A_R$.

Finally, we can substitute this condition into our equivalence relation: $$G_L P_1 G_R = P_2 \implies A_L D_L P_1 A_R D_R = P_2 \implies A_L D_L P_1 A_R (A_R^{-1} P_1^{-1}D_L^{-1} P_1 A_R) = P_2 \implies A_L P_1 A_R = P_2.$$

This proves that $P_1 \equiv_{1.5} P_2 \implies P_1 \equiv_{1} P_2$.

And from our earlier discussion can see that $P_1 \equiv_1 P_2 \iff P_1 \equiv_{1.5} P_2$.