I would like to know if there exists an $n$-qubit (for $n \geq 2$) quantum gate $G_n$ that preserves both $X$ and $Z$ errors and that is additionnally non-Clifford.

In other words, I would like that $G_n$ satisfy

$$ \forall P^X_n, \exists E^X_n | \ G_n P^X_n = E^X_n G_n $$ $$ \forall P^Z_n, \exists E^Z_n | \ G_n P^Z_n = E^Z_n G_n $$


  • $P^X_n$ is any $n$-qubit Pauli matrix composed of $X$ and $I$ terms only.
  • $E_n^X$ is an operator that once decomposed on the Pauli matrices can be expressed as a linear combination composed of terms involving pauli $X$ and identity. The coefficients in this linear combination don't have to be identical.

Similarly, for $Z$ errors.

To be a little bit clearer, $P_2^X$ could be $X_1 X_2$ or $I_1 X_2$ but not $Z_1 X_2$. $E_2^X$ could be $X_1 X_2 + I_1 X_2$, $X_1 X_2 + \frac{1}{3}I_1 X_2$ but not $X_1 X_2 + Z_1 X_2$ (the example I give here might not work strictly speaking as $G_n$ is unitary, but this is just to say that any linear combination is allowed as long as it only involves I and $X$ operators, I do not ask all the coefficients in the linear combination to be equal, even up to a sign). The fact that I am asking the gate to be non-Clifford implies that there exist at least one $E_n^X$ or one $E_n^Z$ that is not a Pauli operator.

As examples of gates that fulfill some but not all of my properties there is:

  • CNOT gate. It preserves both $X$ and $Z$ errors but the $E_2^X$ and $E_2^Z$ will always be tensor product of Pauli (the gate is Clifford).
  • Toffoli gate. It satisfies the properties for $Z$ errors (and one $E_n^Z$ will be a sum of Paulis but not a Pauli itself: the gate is then non-Clifford). However, it can convert a $X$ error into a $Z$ one.

Do gates satisfying the properties I am looking for exist? If so what are some examples?

  • 2
    $\begingroup$ This is not possible. Any set of Pauli strings built from $I$ and $X$ commute pairwise and hence jointly stabilize a non-trivial subspace. Therefore, any $E_n^X$ that is a sum of $k$ such Pauli strings has $k$ as its eigenvalue. However, $E_n^X=G_nP_n^X G_n^\dagger$, so $E_n^X$ is unitary. Therefore, $k=1$ and $E_n^X$ is itself a Pauli string. The same applies to $E_n^Z$. Finally, $P_n^X$ and $P_n^Z$ generate the full Pauli group, so $G_n$ is Clifford. $\square$ Perhaps, you meant for $E_n^X$ to be a linear combination rather than a sum? $\endgroup$ Commented Oct 14, 2022 at 17:50
  • $\begingroup$ @AdamZalcman I am trying to understand your comment but I can already answer your last line. I meant any linear combination (if by sum you mean all the coefficient in this linear combination to be identical, in my case I can allow for any coefficients appearing, they don't have to all be equal). I edit to clarify. $\endgroup$ Commented Oct 14, 2022 at 19:04
  • $\begingroup$ @AdamZalcman Ok I think I see your point. Thanks for your comment. I confirm that the cases I am interested in are when $E_n^X$ is a linear combination of Pauli (hence the coefficients in this combination are not necessarily all the same). Because of that, as you already identified, your proof doesn't seem to apply. For instance, calling $T$ the Toffoli gate, the qubits $1$ and $2$ are the control, we have: $T Z_3 T^{\dagger}=(1/2)( Z_3+Z_2Z_3+Z_1Z_3-Z_1Z_2Z_3)$. I am then wondering if we can preserve both $X$ and $Z$ while being non Clifford. $\endgroup$ Commented Oct 16, 2022 at 19:56
  • 1
    $\begingroup$ Interesting problem. If such a $G_n$ exists then it gives you an automorphism of the Pauli group : $x_a=\sum C_{ab} X_b$,$z_a=\sum D_{ab} Z_b$; here $a$ runs over $1 \cdots n$ and $b$ runs over $2^n$ tuples . $C$ and $D$ are $n 2^n$ variables. Properties of the group give you restrictions on these : $x_a z_b x_a = \pm z_b$, $x_a^2=1$, $z_a^2=1$, $trace(x_a)=0$,$trace(z_a)=0$,$\cdots$. These are quadratic constraints, so solving them is probably not easy. If you manage to find a solution then getting $G_n$ should be manageable; $G_n X_a = x_a G_n$, $G_n Z_a=z_a G_n$ are linear constraints. $\endgroup$
    – unknown
    Commented Oct 17, 2022 at 2:19
  • $\begingroup$ @unknown Thank you for the suggestion. I will think about it to establish a proof. $\endgroup$ Commented Oct 24, 2022 at 8:34

1 Answer 1


TL;DR: It turns out that $G_n$ acts as a phased permutation of the computational basis, sending $|x\rangle$ to $(-1)^{s(x)}|\sigma(x)\rangle$ . Similarly, $H^{\otimes n}G_nH^{\otimes n}$ sends $|y\rangle$ to $(-1)^{t(y)}|\tau(y)\rangle$. Moreover, $$ t(y)+x\cdot\tau(y)=y\cdot\sigma^{-1}(x) + s(\sigma^{-1}(x)) $$ for any two $n$-bit strings $x,y\in\mathbb{F}_2^n$. But then $s$ and $\sigma$ are affine functions on $\mathbb{F}_2^n$, so $G_n$ is Clifford.

$G_n$ is a phased permutation

We begin with the observation that $P_n^Z$ and $E_n^Z$ are diagonal in the computational basis. Moreover, all operators $P_n^Z$ form a basis of the real vector space of diagonal Hermitian matrices. Thus, conjugation by $G_n$ maps diagonal matrices to diagonal matrices. Let $\rho$ be the density matrix of a computational basis state. In other words, $\rho$ is a diagonal matrix with a single $1$ on diagonal and all other elements equal to zero. Then $G_n\rho G_n^\dagger$ is also diagonal with a single element equal $1$. Thus, $G_n$ maps computational basis states to computational basis states, i.e. $G_n$ is a "phased permutation gate" $$ G_n|x\rangle = e^{i\theta(x)}|\sigma(x)\rangle\tag1 $$ where $x\in\mathbb{F}_2^n$ is an $n$-bit string, $e^{i\theta(x)}$ is a phase factor and $\sigma\in S_{2^n}$ is a permutation of the computational basis.

$G_n$ is real

Now, consider the matrix $2^nG_n|+\rangle\langle+|G_n^\dagger$. On one hand, its elements are equal to $e^{i\theta(x_i)-i\theta(x_j)}$ for all pairs of $n$-bit strings $x_i$ and $x_j$. On the other hand, the matrix $2^nG_n|+\rangle\langle+|G_n^\dagger=2^n E_n^X$ is a real symmetric matrix. Consequently, the phase factors $e^{i\theta(x)}$ are $\pm 1$. Thus, we can rewrite $(1)$ as $$ G_n|x\rangle = (-1)^{s(x)}|\sigma(x)\rangle\tag{1'} $$ where $s:\mathbb{F}_2^n\to\mathbb{F}_2$. Incidentally, this implies that $G_1$ is a Pauli gate.

$H^{\otimes n}G_nH^{\otimes n}$ is another phased permutation

If $G_n$ preserves $X$- and $Z$-errors then so does $H^{\otimes n}G_nH^{\otimes n}$. Therefore, $$ H^{\otimes n}G_nH^{\otimes n}|y\rangle = (-1)^{t(y)}|\tau(y)\rangle\tag{2} $$ where $t:\mathbb{F}_2^n\to\mathbb{F}_2$ and $\tau\in S_{2^n}$ is a permutation of the computational basis. But then $$ \begin{align} G_nH^{\otimes n}|y\rangle &= (-1)^{t(y)}H^{\otimes n}|\tau(y)\rangle\tag{3.1}\\ G_n\sum_{x\in\mathbb{F}_2^n}(-1)^{x\cdot y}|x\rangle &= (-1)^{t(y)}\sum_{x\in\mathbb{F}_2^n}(-1)^{x\cdot\tau(y)}|x\rangle\tag{3.2}\\ \sum_{x\in\mathbb{F}_2^n}(-1)^{s(x)+x\cdot y}|\sigma(x)\rangle &= \sum_{x\in\mathbb{F}_2^n}(-1)^{t(y)+x\cdot\tau(y)}|x\rangle\tag{3.3}\\ \sum_{x\in\mathbb{F}_2^n}(-1)^{s(\sigma^{-1}(x))+\sigma^{-1}(x)\cdot y}|x\rangle &= \sum_{x\in\mathbb{F}_2^n}(-1)^{t(y)+x\cdot\tau(y)}|x\rangle\tag{3.4}\\ \end{align} $$ where $\cdot$ denotes the dot product in $\mathbb{F}_2^n$. By linear independence we have $$ s(\sigma^{-1}(x))+\sigma^{-1}(x)\cdot y = t(y)+x\cdot\tau(y)\tag{4} $$ for all $x,y\in\mathbb{F}_2^n$.

$G_n$ is Clifford

Setting $u(x)=s(\sigma^{-1}(x))$ and $\upsilon=\sigma^{-1}$, we can rewrite $(4)$ as $$ u(x)+y\cdot\upsilon(x) = t(y)+x\cdot\tau(y).\tag{5} $$ More explicitly, $(5)$ may be written as $$ u(x_1,\dots,x_n)+\sum_{i=1}^n y_i\upsilon_i(x_1,\dots,x_n)= t(y_1,\dots,y_n)+\sum_{i=1}^n x_i\tau_i(y_1,\dots,y_n).\tag{6} $$ By setting all $y_i=0$, we see that $u:\mathbb{F}_2^n\to\mathbb{F}_2$ is affine. By setting a single $y_i=1$ and all others to zero, we see that each $\upsilon_i:\mathbb{F}_2^n\to\mathbb{F}_2$ is affine. Therefore, $\upsilon:\mathbb{F}_2^n\to\mathbb{F}_2^n$ is affine. Hence, $s$ and $\sigma$ are affine. Therefore, $G_n$ is Clifford.

  • 1
    $\begingroup$ Thanks a lot for this very precise answer! It will take me a bit of time to understand all the details, but I will come back to either ask for clarifications or accept the answer if everything is clear in my mind. $\endgroup$ Commented Nov 14, 2022 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.