# Can every unitary be approximated by gates from the Clifford Hierarchy?

For $$k > 1$$, we recursively define $$\mathcal C^{(r)}(n)$$ as $$\mathcal C^{(r)}(n) = \Bigl\{ U \in \mathbf U(2^n) \mathrel{\Big\vert} \forall P \in \mathcal C^{(1)}(n) : U P U^\dagger \in \mathcal C^{(r-1)}(n) \Bigr\}$$ That is, the set of unitaries that, when used to conjugate a Pauli operator, yield an operator at one level lower in the hierarchy. $$\mathcal C^{(1)}(n)$$ is the Pauli group. Define $$\mathcal C^{(\infty)}(n):= \bigcup_{r=1}^\infty \mathcal C^{(r)}(n)$$ Can every unitary in $$\mathbf U(2^n)$$ be approximated by elements of $$\mathcal C^{(\infty)}(n)$$? In other words, is the set $$\mathcal C^{(\infty)}(n)$$ dense in $$\mathbf U(2^n)$$? If not, what is the closure of the set $$\mathcal C^{(\infty)}(n)$$ in $$\mathbf U(2^n)$$.

To be clear, I mean "closure" and "closed" in a geometric/topological sense. (The totally different algebraic question of closure under products is addressed here Is there a closure property for the entire Clifford hierarchy? )

Thoughts so far: Using this definition it is clear that all $$\mathcal C^{(r)}(n)$$ contain the multiplies of the identity $$e^{i \theta} I$$. So the closure is at least one dimensional containing the scalar matrices $$e^{i \theta} I$$.

Specializing to the case $$n=1$$ for ease, it seems that the diagonal matrix $$\begin{bmatrix} \zeta_{2^{r+1}} & 0 \\ 0 & \overline{\zeta_{2^{r+1}}} \end{bmatrix}$$ is in $$\mathcal C^{(r)}(1)$$. So the closure in $$\mathbf U(2)$$ of $$\mathcal C^{(\infty)}(1)$$ should include all matrices of the form $$\begin{bmatrix} e^{i \alpha} & 0 \\ 0 & e^{-i \alpha} \end{bmatrix}$$.

Together with the previous claim, that implies all diagonal matrices in $$\mathbf U(2)$$ should be in the closure of $$\mathcal C^{(\infty)}(1)$$.

Edit: I added the notation $$(n)$$ to emphasize that the Clifford hierarchy is defined for a fixed number of qubits $$n$$.

This is too long for a comment but not an answer.

First we must define some notion of closeness of unitaries. Other metrics should be fine, but operator norm seems like a good one. Now I think your question becomes for all $$U \in U(2^n)$$ and $$\epsilon$$ does there exist a $$V \in \mathcal{C}^{(\infty)}$$ such that $$||U-V||_\infty < \epsilon$$.

From Cui et al. Diagonal matrices in $$U(2^n)$$ with $$2^k$$ root-of-unity entries are all in $$\mathcal{C}^{(\infty)}$$ at some level. This should get you `close' to any diagonal gate in $$U(2^n)$$.

I'll try to give a sketchy proof that $$U$$ exist which are not close to any element in $$\mathcal{C}^{(\infty)}$$. We know that all $$U(2)$$ gates in the Clifford Hierarchy are semi-Clifford and can therefore be written as $$C e^{i\theta P}$$. $$C$$ is a one-qubit Clifford gate and $$P$$ is a non-trivial Pauli gate. $$\theta$$ is restricted, but even if we allow arbitrary $$\theta$$ each $$V_{C,P}(\theta)=C e^{i\theta P}$$ is parameterized by one real variable, $$\theta$$. There are 24 elements (up to phase) in the one-qubit Clifford group. So there are $$3\times 24$$ different $$V_{C,P}$$. (Note I think there are actually $$3\times 6$$ since these aren't all independent, but that doesn't matter for the following argument.) Each $$V_{C,P}$$ is a rotation about some axis and the set of unitaries $$V_{C,P}(\theta)$$ is a circle on the Bloch sphere (or in the space of $$U(2)$$ matrices). Since we have only a finite (at most 72) number of these circles on the sphere there must be some 'gaps' where for some $$U$$, $$||U-V||_\infty > \epsilon$$ for all $$V$$.

• +1 I think your argument is largely solid. One small thing is that I think you are misusing the Bloch sphere. A rotation operator is described by both an axis of rotation and an angle of rotation, not just an axis of rotation, and can instead be represented within a ball with antipodal points on the surface identified. $C e^{i \theta P}$ will trace out some closed loop in that space as $\theta$ goes from $0$ to $2 \pi$ (which may or may not be a circle, I'm not sure). So really you'll have at most $72$ closed loops in this three-dimensional space, and again you can argue there must be gaps. Commented Nov 9, 2023 at 20:05
• Is there any reason why you view your proof as sketchy rather than being a solid proof? It definitely satisfies me (with the small modification given in my comment above). Commented Nov 9, 2023 at 20:06
• @user196574 Perhaps Jonas says the proof is sketchy because it relies on the fact that all gates in the single qubit Clifford hierarchy are semi Clifford. This is true for both the $n=1$ and $n=2$ qubit Clifford hierarchies by arxiv.org/abs/0712.2084. It is conjectured that a corresponding slightly more generalized statement is true for any $n$, but this is a major unsolved problem in quantum information and is known as the generalized semi Clifford conjecture. Commented Nov 9, 2023 at 23:09
• But I think you're probably both right that a very similar proof would work that doesn't need the full power of generalized semi-Clifford conjecture. Basically the idea seems to be that not only is $\mathcal{C}^\infty$ not dense in $U(2^n)$ but in particular the closure of $\mathcal{C}^\infty$ seems to be a union of finitely many, say $N$, tori. The tori are all shifted forms of $T^{2^n}$ the rank $2^n$ maximal torus of $U(2^n)$. Assuming the conjecture it seems that $N$ should be bounded above by $|CL_n|^2|S_{2^n}|=|CL_n|^2 (2^n)!$ where $CL_n$ is n qubit Clifford group. Commented Nov 9, 2023 at 23:21
• @IanGershonTeixeira Thanks. I'm relatively new to the Clifford hierarchy. Would you agree that Jonas's proof means that for $n=1$, $\mathcal C^{(\infty)}$ is not dense in single-qubit gates? I would expect for larger $n>1$ that $\mathcal C^{(\infty)}$ is still not dense in single-qubit gates. Is that not guaranteed by Jonas's argument, and/or is that not sufficient to rule out whether $\mathcal{C}^{(\infty)}$ is dense in $U(2^n)$? Commented Nov 9, 2023 at 23:25