# Is there a closure property for the entire Clifford hierarchy?

### TL;DR

Is the entire Clifford hierarchy (as opposed to any one level), a group?

### Background.

The Clifford hierarchy (on $$n$$ qubits), is a collection of nested subsets $$\mathcal C^{(1)} \subset \mathcal C^{(2)} \subset \mathcal C^{(3)} \subset \cdots \subset \mathbf U(2^n)$$ of the unitary operators on $$n$$ qubits, defined recursively as follows:

• $$\mathcal C^{(1)}$$ is the Pauli group on $$n$$ qubits, i.e., the set of ($$n$$-fold tensor products of) Pauli operators with real or imaginary scalar factors: tensor products of $$\{ \mathbf 1, X, Y, Z \}$$ with a scalar factor of $$\pm 1$$ or $$\pm i$$.

• For $$k > 1$$, we recursively define $$\mathcal C^{(k)}$$ as

$$\mathcal C^{(k)} = \Bigl\{ U \in \mathbf U(2^n) \mathrel{\Big\vert} \forall P \in \mathcal C^{(1)} : U P U^\dagger \in \mathcal C^{(k-1)} \Bigr\}$$ — that is, the set of unitaries that, when used to conjugate a Pauli operator, yields an operator at one level lower in the hierarchy.

So, for example, the Clifford group is the second level of the Clifford hierarchy, $$\mathcal C^{(2)}$$, as any $$U \in \mathcal C^{(2)}$$ maps a Pauli operator to another Pauli operator (i.e., an element of $$\mathcal C^{(1)}$$) by conjugation.

It is well known that $$\mathcal C^{(1)}$$ and $$\mathcal C^{(2)}$$ are groups: it is not difficult to show that they are closed under multiplication. It is also well-known that the other levels of the Clifford hierarchy are not groups. For instance: for any $$k \geqslant 0$$, a $$k$$-controlled NOT operation $$\mathrm{C}^k \mathrm X \;=\; \mathbf 1^{\otimes k+1} +\, \lvert 1 \rangle\!\!\;\langle 1 \rvert^{\otimes k} \otimes \,(X - \mathbf 1)$$ is a member of $$\mathcal C^{(k+1)} \setminus \mathcal C^{(k)}$$, which we can demonstrate by relating these operations to multiply-controlled Z operations $$\mathrm{C}^k \mathrm Z = \mathrm{diag}(+1,\ldots,+1,-1)$$, and considering their relationships to what we now call phase polynomials. However, using a circuit consisting of 3 such gates, we can easily (using standard computation-uncomputation techniques) produce a circuit which can simulate a $$(2k-1)$$-controlled NOT operation, which for $$k > 1$$ does not live in $$\mathcal C^{(k+1)}$$. (The case $$k=2$$ amounts to the fact that the TOFFOLI gate, together with preparation of bits in the 1 state, is universal for classical computation.)

However, just because the higher levels of the Clifford hierarchy are not groups, does not mean that the entire Clifford hierarchy is not a group. After all: the proof I give just above that $$\mathcal C^{(k)}$$ is not a group, establishes this by proving that I can make a product which escapes to some higher level of the Clifford hierarchy.

So: if you multiply two elements of the Clifford hierarchy, do you always get another element of the Clifford hierarchy?

• In your notation, is $\mathrm{C}^k \mathrm X \;=\; \mathbf 1^{\otimes k+1} +\, \lvert 1 \rangle\!\!\;\langle 1 \rvert^{\otimes k} \otimes \,(X - \mathbf 1)$ simply the same as $\mathrm{C}^k \mathrm X \;= \lvert 1 \rangle\!\!\;\langle 1 \rvert^{\otimes k} \otimes \,X$? If so, why not simplify the equation? thanks Commented Aug 13, 2023 at 19:41
• No it isn't. (Consider what these two operators are in the case $k=1$ or $k=2$, by explicitly computing the matrices.) Commented Aug 25, 2023 at 13:16
• Yes sorry, I terribly misread. You are correct. Commented Aug 30, 2023 at 21:33

It is actually possible to show that there is a simple, single-qubit operator (identified in discussion with John van de Wetering), which is a product of elements of $$\mathcal C^{(3)}$$ but which does not lie in the Clifford hierarchy. Let $$T = \sqrt{S} = \mathrm{diag}(1,\sqrt{i\;\!})$$, which is in $$\mathcal C^{(3)}$$. Then we may show that $$U = T H T$$ does not lie in the Clifford hierarchy.

To show this, we rely on the following simple results.

Lemma. Let $$U = VC$$ for unitaries $$U, V \in \mathbf U(2^n)$$ and $$C \in \mathcal C^{(2)}$$, and let $$k \geqslant 2$$. Then: $$U \in \mathcal C^{(k)} \iff V \in \mathcal C^{(k)}$$.

Corrolary. Let $$U = CV$$ for unitaries $$U, V \in \mathbf U(2^n)$$ and $$C \in \mathcal C^{(2)}$$, and let $$k \geqslant 2$$. Then: $$U^\dagger \in \mathcal C^{(k)} \iff V^\dagger \in \mathcal C^{(k)}$$.

We aim to show that $$U$$ is not in any finite level $$k$$ of the Clifford hierarchy, by considering how its acts on $$X$$ by conjugation. It will be convenient to write \begin{aligned} U \;:=\; T H T \;&=\; T \bigl(\tfrac{Z+X}{\sqrt 2}\bigr) T \\[1ex] &=\; \bigl(\tfrac{Z+Q}{\sqrt 2}\bigr) S, \end{aligned} defining $$Q = T X T^\dagger = T^\dagger Y T = (X+Y)\big/\sqrt 2$$ for the sake of brevity. (Note that $$Q$$ is self-adjoint.) Then: \begin{aligned} V \;:\!&=\; U X U^\dagger \\[1ex] &= T H T X T^\dagger H T^\dagger \\[1ex] &= T H \bigl(\tfrac{X+Y}{\sqrt 2}\bigr) H T^\dagger \\[1ex] &= T \bigl(\tfrac{Z-Y}{\sqrt 2}\bigr) T^\dagger \\[1ex] &= T S^\dagger \bigl(\tfrac{Z+X}{\sqrt 2}\bigr) S T^\dagger \\[1ex] &= S^\dagger \bigl(\tfrac{Z+Q}{\sqrt 2}\bigr) S \;=\; S^\dagger U. \end{aligned} Thus, $$U = SV$$, so that if either of $$U^\dagger$$ or $$V^\dagger = V$$ is in some level of the Clifford hierarchy, then so is the other. In particular: if $$U$$ is in level $$k$$ of the Clifford hierarchy, then $$V$$ is in level $$k-1$$, so $$U^\dagger$$ is also in level $$k-1$$ (supposing that $$k-1 \geqslant 2$$). If $$U^\dagger$$ is in level $$k-1$$, then $$W := U^\dagger X U$$ is in level $$k-2$$. We investigate: \begin{aligned} W \;:\!&=\; U^\dagger X U \\[1ex] &=\; T^\dagger H T^\dagger X T H T \\[1ex] &=\; T^\dagger H S^\dagger Q S H T \\[1ex] &=\; T^\dagger H S^\dagger \bigl(\tfrac{X+Y}{\sqrt 2}\bigr) S H T \\[1ex] &=\; T^\dagger H \bigl(\tfrac{X-Y}{\sqrt 2}\bigr)H T \\[1ex] &=\; T^\dagger \bigl(\tfrac{Z+Y}{\sqrt 2}\bigr) T \\[1ex] &=\; \bigl(\tfrac{Z+Q}{\sqrt 2}\bigr) \;=\; U S^\dagger, \end{aligned} so that $$U = W S$$. But this implies that if $$W$$ is in level $$k-2$$ of the Clifford hierarchy, then $$U$$ is in level $$k-2$$ as well (supposing that $$k-2 \geqslant 2$$).

Chaining together the implications, if $$k \geqslant 4$$, and if $$U$$ is in level $$k$$ of the Clifford hierarchy, then it is also in level $$k-2$$ of the Clifford hierarchy. By induction, if $$U$$ is at any level of the Clifford hierarchy, then in particular it is in $$\mathcal C^{(3)}$$, or possibly even in $$\mathcal C^{(2)}$$. That is: $$U$$ is only in the Clifford hierarchy, if it is in the third level.

If $$U \in \mathcal C^{(3)}$$, this would mean that $$V = V^\dagger = U X U^\dagger \in \mathcal C^{(2)}$$. We've established that this holds if and only if $$U^\dagger \in \mathcal C^{(2)}$$, so that in fact $$U \in \mathcal C^{(2)}$$. However, it is easy to see that it is not a Clifford operator; so by contraposition, $$U$$ cannot be in any finite level of the Clifford hierarchy.

• Interesting piece of trivia, also mentioned to me by John van de Wetering: the answer is also 'no' if we consider circuits on qutrits rather than qubits — see [ arXiv:2202.09235 ]. Commented May 20, 2022 at 12:39
• If $U$ is in the $k$ level of the Clifford hierarchy do you know if $U^2$ is always in the Clifford hierarchy as well? Commented Feb 10, 2023 at 1:57
• Turns out this same example works for powers because it shows that $(TH)^2$ is not in the clifford hierarchy since $THTH$ is not in the hierarchy since $THT$ is not in the hierarchy and right multiplication by cliffords preserves hierarchy level see quantumcomputing.stackexchange.com/questions/30154/… Commented Feb 11, 2023 at 21:46