11
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 ]. $\endgroup$ May 20 at 12:39

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.