I denote the $n$-qubit Clifford group as $C_n$ and the $n$-qubit group of all `local Clifford' (LC) unitaries as $C_1^{\otimes n}$ where $C_1 = \langle H, S\rangle$.

It is well known that $C_n$ is a maximal finite group in $U(2^n)$. That is the addition of any $U\in U(2^n)$ which is not in $C_n$ necessarily generates an infinite order group. See, for example, Prove that adding any non Clifford gate to the Clifford group yields a universal gate set and note that an infinite order group is necessary (though not sufficient) for universality.


My question is: what generators can be added to the group $G=C_1^{\otimes 2}$ without creating an infinite-order group? Clearly any element of $C_2$ will generate a finite group so I want to know if any non-Clifford $U\in U(4)$ exist which together with $G$ generate a finite group.

Restrictions on $U$ established so far

I've come up with the following restrictions on $U$:

(1) $U^k = I$ for some finite integer $k$. ($U$ must be finite order)

(2) $U \ne U_A \otimes U_B$ for $U_A,U_B \in U(2)$.

Since $U$ is non-Clifford $U_A$ or $U_B$ must be non-Clifford and $C_1$ with any non-Clifford is infinite order.

(3) $U^m \ne CNOT$ (or any unitary LC equivalent to $CNOT$) for any integer $m>1$.

Any Clifford LC equivalent to $CNOT$ along with $C_1$ on both qubits generates the full two-qubit Clifford group. Since $U$ is non-Clifford, $U$ and $C_1^{\otimes 2}$ generate a group strictly larger than but containing the two-qubit Clifford group. It must therefore be infinite.

(4) $U$ cannot be a controlled-unitary gate $C(V)$ where $V\in U(2)$.

First note that $V$ must be Clifford. If $V$ is not Clifford then we can use the circuit identity $C(V) X_1 C(V) X_1 = V$ where the control of $C(V)$ is on the first qubit and $X_1$ is Pauli $X$ on the first qubit. Now $V$ violates restriction (2) and must generate an infinite group. $V$ cannot be Pauli since $U$ is non-Clifford. The remaining cases ($V$ is a non-Pauli Clifford gate) were verified to generate infinite-order groups by computer (though it's always good to double check my work).

I also found by computer that $\sqrt{\mbox{SWAP}}$ and $G$ generate an infinite order group.

Additionally, once a $U$ is found such that $\langle U, G\rangle$ generates an infinite group, we can immediately exclude any $V\in U(4)$ such that $V^m = (C_a \otimes C_b )U (C_c \otimes C_d)$ where $C_i$ is a local Clifford unitary for any integer $m\ge 1$.

An answer to my question would be to prove that no such $U$ exists or to give an example of a $U$. Additional interesting restrictions are also appreciated.


For the aficionados and aficionadas there is an infinite $U(1)$ center to worry about in the group definitions above. Either include it in the definition of the Clifford groups above, and then mod out by it when calculating the order of the group or use $PU(2^n)$ in all definitions.


While Adam Zalcman's response is a strong contender for best partial answer on StackExchange, Ian Teixeira's appeal to the classification of finite subgroups of $SU(4)$ provides a complete answer. Thanks to everyone who contributed to this post.

My dream was to prove this case ($n=2$) then to extend the proof to all $n$. Currently, I have no idea how to go about this. Anyone reading this who has an idea please add an answer or comment. Thanks.

  • $\begingroup$ so your question is : find $U \in U(4) : U \not \in C_2$ and $<C_1^{\otimes 2},U>$ generate a finite group? $\endgroup$
    – unknown
    Jun 24 at 17:35
  • $\begingroup$ Yes, modulo comments about the trivial $U(1)$ center. $\endgroup$ Jun 24 at 17:39
  • $\begingroup$ This is such a great question! Hopefully there is a nice conceptual answer for any $ SU_{2^n} $ why no non-Clifford finite group contains the local Cliffords $\endgroup$ Jul 8 at 21:45
  • 1
    $\begingroup$ Yes! That is the dream. I originally thought about asking the more general question, but figured it was too difficult. If you make progress on the general case please let me know. $\endgroup$ Jul 9 at 11:23

4 Answers 4



There is no way to add a non Clifford gate to the local Clifford group $ Cl_1^{\otimes 2} $ and get a finite group.

Definitions: A subgroup $ G $ of $ GL_n(\mathbb{C}) $ is reducible if we can write $ \mathbb{C}^n=V_1 \oplus \dots \oplus V_k $ as a direct sum of smaller subspaces such that every $ g \in G $ fixes the subspaces. In other words, for all $ g \in G $ we have $$ g(V_i)=V_i $$ for all $ i $. This is the standard notion of reducibility of a representation.

A subgroup $ G $ of $ GL_n(\mathbb{C}) $ is imprimitive if we can write $ \mathbb{C}^n=V_1 \oplus \dots \oplus V_k $ as a direct sum of smaller subspaces such that every $ g \in G $ just permutes the subspaces. In other words, for any $ g \in G $ the subspaces $ g(V_1) \oplus \dots \oplus g(V_k) $ are just a permutation of $ V_1 \dots V_k $. That is $$ g(V_i)= V_{\sigma(i)} $$ for all $ i $.

If no such decomposition is possible then we say that $ G $ is primitive.

Claim: The only finite subgroups containing $ Cl_1^{\otimes 2} $ are $ Cl_1^{\otimes 2} $ + $ SWAP $ (size of image in $ PU_4 $ is 1152), $ Cl_2 $ (projective size 11520) and of course $ Cl_1^{\otimes 2} $ itself ( projective size 576).

Of course from this claim follows the fact that any subgroup of $ U_4 $ containing all local Cliffords and containing a non-Clifford gate must be infinite.

Proof: Suppose that $ G $ is a finite group containing $ Cl_1^{\otimes 2} $. Then the determinant $ 1 $ subgroup $ sG $ of $ G $ contains the determinant $ 1 $ subgroup $ sCl_1^{\otimes 2} $ of $ Cl_1^{\otimes 2} $ (it is perhaps more airtight to instead define $ sG:=\pi_2^{-1}[\pi_1(G)] $ and $ sCl_1^{\otimes 2}:=\pi_2^{-1}[\pi_1(G)] $ where $ \pi_1: U_4 \to PU_4 $ and $ \pi_2: SU_4 \to PSU_4\cong PU_4 $ are the natural projection maps). $ sCl_1^{\otimes 2} $ is a primitive subgroup of $ SU_4 $. Any group containing a primitive subgroup is itself primitive. So any finite subgroup of $ SU_4 $ containing $ sCl_1^{\otimes 2} $ must be a primitive finite subgroup of $ SU_4 $. The classification of subgroups is essentially due to [Blichfeldt, Finite Collineation Groups, 1917]. But I learned it from Hannany and He https://arxiv.org/abs/hep-th/9905212 which provides explicit matrix generators for all primitive subgroups of $ SU_4 $. On their list $ sCl_1^{\otimes 2} $ is the fourteenth group so I will call it $ G14 $. Any groups containing $ G14 $ must be divisible by the order of $ G14 $. A quick inspection of the orders of the thirty primitive subgroups shows that of those only $$ G14 \subset G21 \subset G29 \subset G30 $$ and $$ G6 $$ have projective size divisible by $ 576 $. $ G14 $ is $ sCl_1^{\otimes 2} $, $ G21 $ is $ sCl_1^{\otimes 2} $ + $ SWAP $, $ G29 $ is the commutator subgroup of $ sCl_2 $ and $ G30 $ is $ sCl_2 $. $ G6 $ is isomorphic to $ Sp_4(3) $. Of these only $ G6 $ is not contained in the Clifford group. Using the function IsomorphicSubgroups() in the software GAP one can check that $ G6 $ has no subgroup isomorphic to $ G14 $. One can check further to verify that of the remaining four groups $ G29 $ does not contain any subgroup isomorphic to $ sCl_1^{\otimes 2} $. This proves the claim.

TLDR: Finite subgroups of $ U_4 $ were classified by a crazy man named Blichfeldt over 100 years ago. His classification shows that there is only one group outside the Clifford group that has the correct order to contain all the local Cliffords. One can rule out this exceptional case using a computer algebra system like GAP.

  • $\begingroup$ Very nice. I have a few comments. First, technically, $\pi_2$ is not an isomorphism, so the definition of $sG$ needs some clarification to be fully rigorous (though I don't anticipate any real issue to arise here). Second, it's probably a good idea to have a look at Blichfeldt's original work. I might be missing something, but it seems to me that Hanany and He's monograph might contain errors. For example, $G1$ and $G3$ in section $3.1.1$ have the same generators but different order. Also, generators $F_1$ and $C$ are identical, but given different symbols. $\endgroup$ Jul 8 at 17:58
  • 1
    $\begingroup$ I agree with your observation that most of the subgroups listed there are ruled out by simple appeal to Lagrange's theorem or are contained in $Cl_2$. $G6$ is an interesting exception. I ruled it out by observing that if two-qubit unitary $U_{AB}$ has finite order $n$ then $\langle 0_B|U_{AB}|0_B\rangle$ is a single-qubit unitary whose finite order divides $n$. Let $C=\mathrm{diag}(1,1,\omega,\omega^2)$ with $\omega=e^{2\pi i/3}$ as in section $3.1$. Then $\langle 0_B|C|0_B\rangle=R_z(2\pi/3)$ which reduces to case $n=3$ in my answer yielding an infinite order element by Niven's theorem. $\endgroup$ Jul 8 at 18:06
  • $\begingroup$ Your second comment about $ G6 $ is interesting. Yes you are right there are definitely typos in Hannany He. $ G3 $ is supposed to include $ F_4 $ as a generator, then it does have the correct order. Another typo is that there is no matrix $ E $ they meant $ V $ in the generator list for $ G6 $. And in general I agree that the proof I've outlined is kind of terrible and not conceptual at all. If I find something better I'll write it down. As for $ \pi_2^{-1} $ this denotes inverse image under the (non-injective) function $ \pi_2 $ and is standard notation, I don't know what your objection is. $\endgroup$ Jul 8 at 20:18
  • $\begingroup$ Oh, I'm used to denoting the inverse imagine of $y$ under $f$ with $f^{-1}[y]$ and having $f^{-1}(y)$ reserved for the inverse of $f$ evaluated at $y$, and similarly for the image. I suppose the collision here is harmless. FWIW, Wikipedia also uses square brackets for image and pre-image. $\endgroup$ Jul 8 at 20:39
  • 2
    $\begingroup$ @JonasAnderson when I first showed this paper to Victor he actually said pretty much the same thing about it being a good idea for me to rewrite it for the quantum information community with standard generators. I actually think that sounds pretty fun. I haven't gone back to Blichfeldt and done a careful check of completeness but FWIW I've got a Google doc with GAP code that does almost all 30 groups and has more standard generators like H ,P, X ,Z, CNOT SWAP I'm happy to share it with you if you're interested $\endgroup$ Jul 9 at 12:29

This partial answer places additional restrictions on $U$.

Constructing unitaries with infinite order

By KAK decomposition, $U$ can be written as

$$ U=(A_1\otimes A_0)e^{i\alpha X\otimes X + i\beta Y\otimes Y + i\gamma Z\otimes Z} (B_1\otimes B_0)\tag1 $$

for $A_i,B_i\in SU(2)$ and $\alpha,\beta,\gamma\in\mathbb{R}$. First, consider the case where $U=e^{i\alpha X\otimes X}$. If $\alpha$ is not a rational multiple of $\pi$ then $U$ has infinite order. Assume then that $\alpha=\frac{m\pi}{n}$ for $m,n$ relatively prime positive integers. Let $k$ be the multiplicative inverse of $m$ in $\mathbb{Z}_n^*$ and define

$$ \begin{align} V&=U^{2k}=\exp\left(\frac{i\pi }{n}X\otimes X\right)\\ W&=(I\otimes H)V(I\otimes H)=\exp\left(\frac{i\pi}{n}X\otimes Z\right).\tag2 \end{align} $$

We have

$$ \begin{align} VW&=\left(\cos\frac{\pi}{n}+i\sin\frac{\pi}{n}X\otimes X\right)\left(\cos\frac{\pi}{n}+i\sin\frac{\pi}{n}X\otimes Z\right)\\ &=\cos^2\frac{\pi}{n}+i\sin\frac{\pi}{n}\left[\cos\frac{\pi}{n}X\otimes X+\cos\frac{\pi}{n}X\otimes Z+\sin\frac{\pi}{n}I\otimes Y\right].\tag3 \end{align} $$

The two-qubit Pauli operators in square brackets square to identity and anti-commute pairwise, so the whole expression in square brackets itself squares to a scalar multiple of identity and we may rewrite $(3)$ as

$$ \begin{align} VW&=\cos\lambda\pi+i\sin\lambda\pi A\\ &=\exp(i\lambda\pi A)\tag4 \end{align} $$

for some $\lambda\in\mathbb{R}$ and some operator $A$ with $A^2=I$. In analogy with the single-qubit case, the last expression for $VW$ may be interpreted as a rotation around the axis $A$ through angle $\lambda/2$.

Now, if $\lambda\notin\mathbb{Q}$ then $VW$ has infinite order. Thus, if $n\in\mathbb{Z}_+$ is such that

$$ \cos^2\frac{\pi}{n}=\cos\lambda\pi\tag5 $$

for an irrational $\lambda$ then $U=e^{i\frac{m\pi}{n}X\otimes X}$ and Hadamard generate an infinite subgroup of $U(4)$.

Special values of $n$

Let's consider a few concrete values of $n$.

  • If $n=1$, then $\lambda=0\in\mathbb{Q}$, but $U=-I\in C_2$.
  • If $n=2$, then $\lambda=\frac12\in\mathbb{Q}$, but $U=iX\otimes X\in C_2$.
  • If $n=3$, then $\cos\lambda\pi=\frac14$ and $\lambda\notin\mathbb{Q}$ by Niven's theorem.
  • If $n=4$, then $\lambda=\frac13\in\mathbb{Q}$, but once again $U=\frac{1+iX\otimes X}{\sqrt2}\in C_2$.
  • If $n=8$, then we can follow the argument in the classical proof that $H$ and $T$ gates are universal for $SU(2)$. Namely, we note that the minimal polynomial of $e^{2\pi i\lambda}$

$$ x^4 + x^3 + \frac14 x^2 + x + 1\tag6 $$

has a coefficient which is not an integer, so the polynomial is not cyclotomic. By theorem B.1 in Appendix B of this paper we conclude that $\lambda\notin\mathbb{Q}$.

If $n$ is divisible by $8$ or $3$, then we can reduce to one of the cases above by raising $V$ and $W$ to the appropriate power. In general, we can reduce the case of an arbitrary integer $n$ to the case corresponding to any of its prime divisors.

Primes checked on computer

We can check if some of the odd primes greater than $3$ give rise to an infinite order unitary using the following python script

import sympy

# Strictly speaking, we only need to look at prime n, but
# we can also check equation (6) while we're at it.
for n in [2, 3, 4, 5, 6, 7, 8] + [sympy.prime(i) for i in range(5, 100)]:
    c = sympy.cos(sympy.pi / n)
    a = (c ** 2 + sympy.I * sympy.sqrt(1 - c ** 4)) ** 2
    m = sympy.AlgebraicNumber(a).minpoly.monic()
    coeffs = m.all_coeffs()
    print(not all(c.is_integer for c in coeffs), n, coeffs)

which computed

False 2 [1, 1]
True 3 [1, 7/4, 1]
False 4 [1, 1, 1]
True 5 [1, 9/4, 41/16, 9/4, 1]
True 6 [1, -1/4, 1]
True 7 [1, 11/4, 29/8, 239/64, 29/8, 11/4, 1]
True 8 [1, 1, 1/4, 1, 1]
True 11 [1, 15/4, 13/2, 493/64, 2027/256, 8119/1024, 2027/256, 493/64, 13/2, 15/4, 1]
True 13 [1, 17/4, 133/16, 43/4, 1467/128, 11827/1024, 47321/4096, 11827/1024, 1467/128, 43/4, 133/16, 17/4, 1]
True 17 [1, 21/4, 203/16, 627/32, 5951/256, 12463/512, 50209/2048, 100469/4096, 1607521/65536, 100469/4096, 50209/2048, 12463/512, 5951/256, 627/32, 203/16, 21/4, 1]
True 19 [1, 23/4, 61/4, 1641/64, 8293/256, 35889/1024, 9129/256, 292755/8192, 2342325/65536, 9369319/262144, 2342325/65536, 292755/8192, 9129/256, 35889/1024, 8293/256, 1641/64, 61/4, 23/4, 1]
True 23 [1, 27/4, 169/8, 2663/64, 959/16, 18081/256, 38255/512, 1240605/16384, 4972287/65536, 19892437/262144, 39785127/524288, 318281039/4194304, 39785127/524288, 19892437/262144, 4972287/65536, 1240605/16384, 38255/512, 18081/256, 959/16, 2663/64, 169/8, 27/4, 1]
True 29 [1, 33/4, 509/16, 617/8, 17209/128, 189031/1024, 883405/4096, 939607/4096, 7657361/32768, 30751215/131072, 123075359/524288, 15385221/65536, 984656783/4194304, 15754509543/67108864, 63018038201/268435456, 15754509543/67108864, 984656783/4194304, 15385221/65536, 123075359/524288, 30751215/131072, 7657361/32768, 939607/4096, 883405/4096, 189031/1024, 17209/128, 617/8, 509/16, 33/4, 1]
True 31 [1, 35/4, 287/8, 5923/64, 21921/128, 126899/512, 308699/1024, 5386235/16384, 11102899/32768, 44762051/131072, 89654271/262144, 717364337/2097152, 1434749227/4194304, 5739000597/16777216, 11478001349/33554432, 367296043199/1073741824, 11478001349/33554432, 5739000597/16777216, 1434749227/4194304, 717364337/2097152, 89654271/262144, 44762051/131072, 11102899/32768, 5386235/16384, 308699/1024, 126899/512, 21921/128, 5923/64, 287/8, 35/4, 1]
True 37 [1, 41/4, 793/16, 2421/16, 10577/32, 571305/1024, 3164007/4096, 118491/128, 66143577/65536, 273701283/262144, 1106365967/1048576, 1109114697/1048576, 4438382899/4194304, 35508987303/33554432, 142036606517/134217728, 71018321185/67108864, 4545172591693/4294967296, 18180690368881/17179869184, 72722761475561/68719476736, 18180690368881/17179869184, 4545172591693/4294967296, 71018321185/67108864, 142036606517/134217728, 35508987303/33554432, 4438382899/4194304, 1109114697/1048576, 1106365967/1048576, 273701283/262144, 66143577/65536, 118491/128, 3164007/4096, 571305/1024, 10577/32, 2421/16, 793/16, 41/4, 1]
True 41 [1, 45/4, 959/16, 6469/32, 124937/256, 232275/256, 702227/512, 1809903/1024, 33270951/16384, 568272741/262144, 2331750279/1048576, 4700829213/2097152, 37680003819/16777216, 9423427581/4194304, 150782456021/67108864, 301566434987/134217728, 9650129270063/4294967296, 38600517671513/17179869184, 154402070746035/68719476736, 308804141493505/137438953472, 2470433131948081/1099511627776, 308804141493505/137438953472, 154402070746035/68719476736, 38600517671513/17179869184, 9650129270063/4294967296, 301566434987/134217728, 150782456021/67108864, 9423427581/4194304, 37680003819/16777216, 4700829213/2097152, 2331750279/1048576, 568272741/262144, 33270951/16384, 1809903/1024, 702227/512, 232275/256, 124937/256, 6469/32, 959/16, 45/4, 1]
True 43 [1, 47/4, 131/2, 14813/64, 149939/256, 1167743/1024, 1843187/1024, 4932729/2048, 46690691/16384, 203346617/65536, 52721183/16384, 13669999493/4194304, 54875745797/16777216, 219674638973/67108864, 219703389203/67108864, 878827931927/268435456, 14061267674887/4294967296, 56245075867073/17179869184, 28122538036887/8589934592, 899921217256537/274877906944, 3599684869029459/1099511627776, 14398739476117879/4398046511104, 3599684869029459/1099511627776, 899921217256537/274877906944, 28122538036887/8589934592, 56245075867073/17179869184, 14061267674887/4294967296, 878827931927/268435456, 219703389203/67108864, 219674638973/67108864, 54875745797/16777216, 13669999493/4194304, 52721183/16384, 203346617/65536, 46690691/16384, 4932729/2048, 1843187/1024, 1167743/1024, 149939/256, 14813/64, 131/2, 47/4, 1]

showing that if $n$ is divisible by $8$ or by any odd prime up to $43$ then $VW$ has infinite order.

Proof sketch for all odd primes

The output above suggests an approach to proving that $\lambda\notin\mathbb{Q}$ when $n$ is any odd prime using a little bit of algebraic number theory. Specifically, the output suggests that the second coefficient of the monic minimal polynomial of $e^{2\pi i\lambda}$ is $\frac{p+4}{4}$. We will sketch a proof that this is indeed the case for all odd primes $p$.

Let $K$ denote the splitting field of the minimal polynomial of $e^{2\pi i\lambda}$. The second coefficient of the polynomial is equal to the negative trace of $e^{2\pi i\lambda}$ relative to the field extension $K/\mathbb{Q}$. On the other hand, the trace is the sum of all elements of $K$ conjugate to $e^{2\pi i\lambda}$. In this case, the conjugates are $e^{2\pi i\lambda_k}$ for $k=1,2,\dots,p-1$ where

$$ \cos^2\frac{k\pi}{n}=\cos\lambda_k\pi.\tag7 $$

Therefore, the trace of $e^{2\pi i\lambda}$ relative to the field extension $K/\mathbb{Q}$ is

$$ \begin{align} \mathrm{tr}_{K/\mathbb{Q}}(e^{2\pi i\lambda})&=\sum_{k=1}^{p-1}e^{2\pi i\lambda_k}\\ &=\sum_{k=1}^{p-1}(2\cos^4\frac{\pi k}{p}-1)\\ &=1-p+2\sum_{k=1}^{p-1}\cos^4\frac{\pi k}{p}\\ &=1-p+\frac14\sum_{k=1}^{p-1}\left(3+4\cos\frac{2\pi k}{p}+\cos\frac{4\pi k}{p}\right)\\ &=\frac14-\frac{p}{4}+\sum_{k=1}^{p-1}\cos\frac{2\pi k}{p} + \frac14\sum_{k=1}^{p-1}\cos\frac{4\pi k}{p}\\ &=\frac14-\frac{p}{4}+\sum_{k=0}^{p-1}e^{\frac{2\pi ik}{p}} - 1 + \frac14\left(\sum_{k=0}^{p-1}e^{\frac{4\pi ik}{p}} - 1\right)\\ &=\frac14-\frac{p}{4}-1-\frac14\\ &=-\frac{p+4}{4} \end{align}\tag8 $$

which agrees with the computer output for odd primes from $3$ to $43$. Thus, the second coefficient of the monic minimal polynomial of $e^{2\pi i\lambda}$ is $\frac{p+4}{4}$ which is not an integer. Therefore, the polynomial is not cyclotomic, so by the previously cited theorem B.1 in Appendix B of this paper we have $\lambda\notin\mathbb{Q}$.


We have shown that if $\alpha\in\{0, \frac{\pi}{4},\frac{\pi}{2},\frac{3\pi}{4},\pi\}$ then $U=e^{i\alpha X\otimes X}\in C_2$ and otherwise $\langle U,H\rangle$ has infinite order. Moreover, $X\otimes X$, $Y\otimes Y$ and $Z\otimes Z$ commute pairwise and exponentiate to single-parameter subgroups of $U(4)$ that coincide only at identity. Therefore, we conclude that every unitary of the form

$$ U=e^{i\alpha X\otimes X + i\beta Y\otimes Y + i\gamma Z\otimes Z}\tag9 $$

either belongs to $C_2$ or $\langle U, H\rangle$ has infinite order. It is easy to further extend the conclusion to unitaries of the form $(1)$ with local unitaries equivalent up to local Cliffords in the sense that $A_iB_i\in C_1$.

This leaves the case of general local unitaries $A_i,B_i$ unresolved. Nevertheless, it appears unlikely that there exists a finite subgroup of $U(4)$ that contains $C_1^{\otimes 2}$ and is not contained in $C_2$.

  • 1
    $\begingroup$ Thank you. This is great. The space of possible counter examples is vastly reduced. $\endgroup$ Jun 27 at 4:39
  • $\begingroup$ Thank you for posting a fascinating problem! :-) $\endgroup$ Jun 27 at 5:22
  • 1
    $\begingroup$ A very slight extension: let $S=\{V | V H V^{\dagger} \in C_1 \}$ (where $V \in U(2)$). Then if $A_0 \in S$, $A_1 \in U(2)$, and $B_i= A_i^{\dagger}$ we have an isomorphic group and $I\otimes H$ is mapped to an LC unitary. $\endgroup$ Jun 27 at 14:09
  • $\begingroup$ Nice. Ultimately, however, I doubt this type of trick will take us to the most general solution. I think the core "reason" the desired $U$ does not exist has to do with the properties of trigonometric functions. Specifically, they tend to map rational numbers to irrational numbers (see Niven's theorem). As a consequence, composing rational rotations around different axes yields an irrational rotation. That's what Hadamard does in the proof: it takes (a power of) $U$ and produces a rotation around a different axis. Even though both rotations are rational, their composition is not. $\endgroup$ Jun 27 at 17:42
  • $\begingroup$ In order to get to the general solution, I think we need to write $A_i,B_i$ as $\cos\theta+i\sin\theta(n_xX+n_yY+n_zZ)$, plug them into $(1)$ and write down construction similar to $(3)$ (but of course more complicated due to a greater number of angles involved). Next, we need to use algebraic number theory again to prove that the resulting operation is a rotation by an irrational multiple of $\pi$ and hence infinite order. I see two difficulties to overcome: coming up with an expression that makes a rotation and technical difficulty due to constraints more complicated than $(5)$. $\endgroup$ Jun 27 at 17:48

This is a comment on Adam's answer which is too long to post as a comment.

Starting with Adam's hint:

``I see two difficulties to overcome: coming up with an expression that makes a rotation and technical difficulty due to constraints more complicated than (5).''

The two difficulties are interconnected, but when I can express the relevant unitaries as rotations the technical difficulties can be overcome. This results in a simple expression for the second coefficient of the monic minimal polynomial.

This following proof is very similar to Adam's proof. I think new proof ingredients will be necessary for the cases where $U$ cannot be expressed as a rotation. I include my modest progress here in hopes that it is useful in extending this proof to the general case.

A More General Proof

Let $H$ be a Hermitian matrix such that \begin{equation} H = \sum_{i=1}^{M} \alpha_i P_i \end{equation} where $i$ is a sum over $M$ unique and non-trivial Pauli matrices on $N$ qubits, $\alpha_i \in \mathbb{R}$ (since $H$ is Hermitian), and $H$ has the additional requirement that $H^2 = I$. We also have that $\sum_i^M \alpha_i^2 = 1$.

Now, define $\vec{\alpha}$ to be the vector of coefficients $\alpha_i$.

Let $U$ be a finite-order matrix in $SU(2^N)$. $U$ can be thought of as a rotation about $H$. Then \begin{equation} U = e^{i\frac{m\pi}{n} H} = \cos \frac{m\pi}{n} I + i \sin \frac{m\pi}{n} H. \end{equation}

Let $k$ be the multiplicative inverse of $m$ in $\mathbb{Z}^*_n$ and then define \begin{equation} V=U^k = \pm e^{i\frac{\pi}{n} H}. \end{equation}

Choose $C\in C_1^{\otimes n}$ such that $[V, CVC^{\dagger}]\ne 0$ and $VCVC^{\dagger}=e^{i\lambda A}$ for some Hermitian matrix $A$ with $A^2 = I$. I'm not sure under what conditions such a $C$ exists and for now I'll assume we can find such a $C$. I'll discuss some slight extensions to this at the end.

Define $W=CVC^{\dagger}$. Note that conjugation by Clifford permutes the entries in $\vec{\alpha}$ (and potentially applies a $\pm 1$ to some entries) resulting in a new vector which we will call $\vec{\beta}$. Since $VW=e^{i\lambda A}$ we must have

\begin{align*} VW &= \left(\cos \frac{\pi}{n} I + i\sin \frac{\pi}{n} \sum_{i=1}^{M} \alpha_i P_i\right)\left(\cos \frac{\pi}{n}I + i\sin \frac{\pi}{n} \sum_{j=1}^{M} \beta_j P_j\right) \\ &= (\cos^2 \frac{\pi}{n} - \sin^2 \frac{\pi}{n}\kappa)I + i\sin \frac{\pi}{n} \tilde{A} \end{align*} where $\kappa$ is a constant which is the sum of all terms $\alpha_i \beta_j$ when $P_i = P_j$ and $\tilde{A}^2 \propto I$. Note, if $C$ permutes the non-zero entries of $\vec{\alpha}$ this equation is satisfied.

Now since $VW$ is a rotation about some axis, $A$ we have that \begin{equation} (\cos^2 \frac{\pi}{n} - \sin^2 \frac{\pi}{n}\kappa) = (1+\kappa)\cos^2 \frac{\pi}{n} - \kappa = \cos \lambda \pi \end{equation} for some $\lambda \in [0,2)$.

For various values of $n,\kappa$ we want to know if/when $\lambda$ is a rational angle. When this is the case $VW$ has finite order. Otherwise it has infinite order. As before we will look at the minimal polynomials of $e^{2\pi i \lambda_n}$ which we can write as

\begin{align*} e^{2\pi i \lambda_n} &= \left[\left((1+\kappa)\cos^2 \frac{\pi}{n} - \kappa\right) + i\left(1-\left[(1+\kappa)\cos^2 \frac{\pi}{n} - \kappa\right]^2\right)^{\frac{1}{2}}\right]^2 \\ &= (1+\kappa)^2 \cos^4 \frac{\pi}{n} - 2\kappa (1+\kappa)\cos^2 \frac{\pi}{n} +\kappa^2 - \left(1-\left[(1+\kappa)\cos^2 \frac{\pi}{n} - \kappa\right]^2\right) + i[\;] \\ &= (1+\kappa)^2 \cos^4 \frac{\pi}{n} - 2\kappa (1+\kappa)\cos^2 \frac{\pi}{n} +\kappa^2 - 1 + (1+\kappa)^2\cos^4 \frac{\pi}{n} - 2 \kappa (1+\kappa) \cos^2 \frac{\pi}{n} + \kappa^2 + i[\;] \\ &= 2(1+\kappa)^2 \cos^4 \frac{\pi}{n} - 4\kappa (1+\kappa)\cos^2 \frac{\pi}{n} + 2\kappa^2 - 1 + i[\;] \\ \end{align*} where $i[\;]$ indicates purely imaginary terms.

We will again prove that when $n$ is an odd prime $p$ that $\lambda$ is (with few exceptions) irrational. Since $\lambda$ is rational when all coefficients of the minimal monic polynomial are integer, it is sufficient to prove irrationality of $\lambda$ by showing that any coefficient is non-integer. Since the field trace is equal to $-1$ times the second-highest-order coefficient we can again use it to prove irrationality in many cases. The trace of $e^{2\pi i \lambda}$ relative to the field extension $K/\mathbb{Q}$ is

\begin{align*} \mbox{tr}_{K/\mathbb{Q}}(e^{2\pi i \lambda}) &= \sum_{k=1}^{p-1}\left( 2(1+\kappa)^2 \cos^4 \frac{\pi}{n} - 4\kappa (1+\kappa)\cos^2 \frac{\pi}{n} + 2\kappa^2 - 1\right) \\ &= 2(1+\kappa)^2\sum_{k=1}^{p-1}\cos^4 \frac{\pi}{n} - 4\kappa (1+\kappa)\sum_{k=1}^{p-1}\cos^2 \frac{\pi}{n} + (2\kappa^2 - 1)(p-1) \\ &= (1+\kappa)^2(\frac{3}{4}p - 2) + 2\kappa(1+\kappa)(p-2) + (2\kappa^2 - 1)(p-1)\\ &= -1 + \frac{1}{4}(\kappa - 1)(3\kappa + 1)p.\\ \end{align*} We see that when $\kappa = 0$ we recover the original answer. I believe we can always choose $V$ or $V^\dagger$ (or $W$ or $W^\dagger$) such that there's an equivalent expression with $\kappa \ge 0$. Also, generally $\kappa \le 1$. Note that I haven't specified the number of qubits so this works for any number of qubits when the aforementioned conditions are met.

Then, we have to show that all integer solutions to the above equation correspond to $U$ being a Clifford (or have other non-integer coefficients in its minimal monic polynomial). Finally, $n=2^t$ must be handled separately. (I still need to verify these cases.)

While this extends the proof to more general $U$, it does not extend the proof to a general $U\in SU(4)$.


We can extend this to unitaries of the form \begin{equation} U=\prod_j e^{i\pi \frac{m_j}{n_j} H_j} \end{equation} where $H_j^2 = I$ and $[H_i,H_j]=0$ for all $i,j$.

We can also allow \begin{equation} VW=\prod_j e^{i\lambda_j A_j} \end{equation} where $A_j^2 = I$ and $[A_i,A_j]=0$ for all $i,j$.

Note, the conditions for which $C$s can produce such a $VW=VCVC^{\dagger}$ will become more complicated.


Here's an example for the real Pauli and Clifford groups : $$P_1=<X_1,Z_1>; |P_1|=8;$$ $$P_2=<X_1,Z_1,X_2,Z_2>; |P_2|=32;$$ $$C_1=<X_1,Z_1,H_1>; |C_1|=16;$$ $$C_1^{\otimes 2}=<X_1,Z_1,H_1,X_2,Z_2,H_2>; |C_1^{\otimes 2}|=128;$$ $$C_2=<X_1,Z_1,H_1,X_2,Z_2,H_2,I \oplus Z>; |C_2|=2304;$$ $$D_2=<X_1,Z_1,H_1,X_2,Z_2,H_2,ZH \oplus Z>; |D_2|=2304;$$

The last generator for $C_2$ is just the CZ gate; $C_2$ maps $P_2$ to itself under conjugation. $D_2$ doesn't. So $U = ZH \oplus Z$ would satisfy what you're looking; it is also orthogonal.

  • $\begingroup$ The (complex) Clifford group I'm referring to has $C_1= \langle S, H \rangle$ where $S=diag(1,i)$. I believe this definition is standard, but I should have been more clear. The $C_1$ you've written is not a maximal finite subgroup of $U(2,\mathbb{C})$ since $S$ can be added to it. With LC operations from the complex $C_1$ we can see that $(S^3 X \otimes S^3) U^2 (X\otimes S) = C(X)$ for your $U$ above. If $U$ is non-Clifford as you claim then $U$ will violate restriction (3) above and must generate an infinite group with $C_1 \otimes C_1$ as I've defined $C_1$. $\endgroup$ Jun 25 at 9:57
  • $\begingroup$ The example is for the real Paul and Clifford groups; $U$ is "non-clifford" in that setting. The real example was quick to find; I expect the complex to be more difficult...I'll look if I have time $\endgroup$
    – unknown
    Jun 25 at 15:14
  • $\begingroup$ I believe $U$ is non-Clifford in both settings. It's that $C_1$ isn't a maximal finite subgroup to begin with and the question becomes less interesting. $\endgroup$ Jun 25 at 19:19
  • $\begingroup$ If you have time, definitely take a look at the complex case. I'm very interested in your findings. $\endgroup$ Jun 25 at 19:55
  • $\begingroup$ @JonasAnderson, I think real $C_1$ is probably maximal in orthogonal group. The complex case looks a lot different. It doesn't look possible; this paper shows that "any entangling gate is universal"...arxiv.org/abs/quant-ph/0207072 ...it might give clues for a formal proof $\endgroup$
    – unknown
    Jun 27 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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