Is there a closure property for the entire Clifford hierarchy?

Question

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?

Answer 1

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.