# Inverses and the Clifford Hierarchy

Elements of the (qubit) Clifford Hierarchy are unitary matrices. For a good definition of the Clifford Hierarchy see: Is there a closure property for the entire Clifford hierarchy?

While a complete structure theorem for the Clifford Hierarchy, $$\mathcal{CH}$$, is still lacking, can we prove that if $$U\in \mathcal{CH}$$ then $$U^{\dagger}\in \mathcal{CH}$$?

### $$U$$ is semi-Clifford

Semi-Clifford means that $$U = C_L D C_R$$ where $$C_L, C_R$$ are Clifford and $$D$$ is a diagonal gate in $$\mathcal{CH}$$.

Then, $$U^\dagger = C_R^\dagger D^\dagger C_L^\dagger$$. By [1] the diagonal gate in level k form a group so the inverse of $$D$$ is also in level $$k$$. Each level of the Clifford Hierarchy is closed under left and right multiplication by Clifford gates. So in this case $$U^\dagger$$ is even in the same level of $$\mathcal{CH}$$ as $$U$$.

### $$U$$ is generalized semi-Clifford

Generalized semi-Clifford means that $$U = C_L P D C_R$$ where $$C_L, C_R$$ are Clifford, $$D$$ is a diagonal gate in $$\mathcal{CH}$$, and $$P$$ is a permutation (on states) in $$\mathcal{CH}$$. This was proven in [2].

In this case, $$U^\dagger = C_R^\dagger D^\dagger P^\dagger C_L^\dagger = C_R^\dagger P^\dagger (P D^\dagger P^\dagger) C_L^\dagger$$. And since the term in parentheses is a diagonal matrix with the same $$2^k$$ root-of-unity entries as $$D$$, it must be in $$\mathcal{CH}$$ (since $$D$$ is in $$\mathcal{CH}$$). We can also see that $$U^\dagger$$ must be generalized semi-Clifford and $$U^\dagger$$ is in $$\mathcal{CH}$$ iff $$P^\dagger$$ is in $$\mathcal{CH}$$. To complete the proof of this case I need to show that $$P^\dagger$$ is in $$\mathcal{CH}$$ which I currently do not know how to do.

### General $$U$$

It is not known if all elements in $$\mathcal{CH}$$ are generalized semi-Clifford. Nevertheless, we may be able to prove (or disprove) this conjecture for general $$U \in \mathcal{CH}$$.
• +1 great question! I just got back from thailand so I've been away from QCSE and arXiv so first of all congrats on posting your preprint (reference [2] in this question) it looks great! Anyway, I think that asking for closure under inverses is the most natural follow up to quantumcomputing.stackexchange.com/questions/26499/… where it is shown that the Clifford hierarchy is not closed under products. Wish I'd thought to ask this! I'll put a bounty on this soon if it doesn't get any action Feb 8 at 18:25
• For the semi-clifford case you use that the Clifford group is closed under inverses and the diagonal gates in the $k$ th level of the hierarchy are closed under inverses, but I feel like you need to mention a final step which is that the $k$ level of the Clifford hierarchy is closed under left and right multiplication by Clifford gates e.g. proposition 3 of arxiv.org/abs/0712.2084. Since $D^\dagger$ is in the $k$ level and $C_R^\dagger, C_L^\dagger$ are Clifford then the product $U^\dagger = C_R^\dagger D^\dagger C_L^\dagger$ is also in the $k$ level of the hierarchy. Feb 8 at 18:38
• Or are you making some stronger claim that the entire group generated by the level k diagonal gates together with the Clifford gates actually is contained in level k? Feb 8 at 18:42
• You're correct. I'm making use of the proof that left and right multiplication by Clifford gates preserve the level in $\mathcal{CH}$. For clarity I should definitely mention that. Thanks for pointing it out. Feb 10 at 4:56
• I think I found an order 3 permutation in the third level of CH. Let CCX(c,c,t) and CX(c,t) denote the controlled-controlled not and the controlled not gates, respectively. And let c and t denote the qubits that the controls and targets act upon. Then, I claim that CCX(1,2,3)CX(3,4)CX(4,3) is an order three permutation at the third level in CH. Feb 14 at 21:40

This partial answer breaks the question of the closure of the levels of the Clifford hierarchy under inversion into two parts: the easy question of closure under complex conjugation and the harder question of closure under transposition. It also offers a proof of the former and an informal argument for the latter.

Lemma 1 (Every level of the Clifford hierarchy is closed under complex conjugation)
For every $$k\geqslant 1$$, we have $$U\in\mathcal{C}^{(k)}\iff\overline{U}\in\mathcal{C}^{(k)}.\tag1$$ Proof. Equivalence $$(1)$$ is obviously true for every $$U$$ in the Pauli group $$\mathcal{C}^{(1)}$$. Assume that $$(1)$$ holds for $$k$$ and let $$U\in\mathcal{C}^{(k+1)}$$ and $$P\in\mathcal{C}^{(1)}$$. By definition $$UPU^\dagger=V\in\mathcal{C}^{(k)}$$. But then $$\overline{U}P\overline{U}^\dagger=\pm \overline{U}\overline{P}\overline{U}^\dagger=\pm\overline{(UPU^\dagger)}=\pm\overline{V}\in\mathcal{C}^{(k)}\tag2$$ so $$\overline{U}\in\mathcal{C}^{(k+1)}$$. $$\square$$

This immediately gives us

Corollary 2 (Symmetric subset of every level is closed under inversion)
If $$U=e^{i\theta}U^T$$ for some $$\theta\in[0,2\pi)$$, then $$U\in\mathcal{C}^{(k)}\iff U^\dagger\in\mathcal{C}^{(k)}\tag3$$ for every $$k\geqslant 1$$.

This provides a simple alternative route to closure under inversion for diagonal gates and extends it to gates such as $$\sqrt{\text{iSWAP}}$$ and various other swap gates. In fact, $$(3)$$ applies to every gate whose Pauli expansion consists of terms for which the parity of the number of $$Y$$ operators is the same (either all even or all odd). Unfortunately, this set does not include all permutations.

Conjecture 3 (Every level is closed under transposition)
For every $$k\geqslant 1$$, we have $$U\in\mathcal{C}^{(k)}\iff U^T\in\mathcal{C}^{(k)}\tag4.$$

Informal argument. Clifford hierarchy arises as the set of gates that admit fault-tolerant implementation using gate teleportation, see page $$3$$ in "Quantum teleportation is a universal computational primitive". The protocol is summarized in figure $$2$$ of the paper

The protocol consists of two stages. In the first stage, we prepare $$n$$ Bell pairs $$|\Phi^n\rangle$$ and apply the desired gate $$U\in\mathcal{C}^{(k)}$$ to one half of the Bell pairs obtaining $$|\Psi^n_U\rangle=(I\otimes U)|\Psi^n\rangle.\tag5$$ In the second stage, we perform Bell measurements $$B$$ on the input state $$|\alpha\rangle$$ and the other half of the state created in $$(5)$$ and finally apply corrections conditioned on the measurement outcomes using $$R'^\dagger_{xz}\in\mathcal{C}^{(k-1)}$$.

Now, it is easy to check that $$|\Psi^n_U\rangle=(U^T\otimes I)|\Psi^n\rangle.\tag6$$ Thus, two changes are needed in the protocol above to effect $$U^T$$ rather than $$U$$. First, we can apply $$U$$ on the middle qubit rather than the bottom qubit (or alternatively apply $$U^T$$ to the bottom qubit). Second, replace the $$R'_{xz}=UR_{xz}U^\dagger$$ correction with the $$R''_{xz}=U^TR_{xz}\overline{U}$$ correction.

We know that $$R'_{xz}\in\mathcal{C}^{(k-1)}$$, but we don't know whether $$R''_{xz}\in\mathcal{C}^{(k-1)}$$. However, one of the changes to the protocol necessary to effect $$U^T$$ rather than $$U$$ is operationally very simple: apply $$U$$ on a different qubit. One might then suspect that the associated update to the correction isn't too complicated and in particular, the correction stays in $$\mathcal{C}^{(k-1)}$$. I don't know how to prove this at the moment, though. $$\square$$

Lemma 1 and Conjecture 3 combine to give us

Corollary 4 (Every level is closed under inversion)
For every $$k\geqslant 1$$, we have $$U\in\mathcal{C}^{(k)}\iff U^\dagger\in\mathcal{C}^{(k)}\tag7.$$

• oh dang sorry the bounty expired, I would have totally awarded it to you, this answer looks really fun! Feb 18 at 1:13
• This is a significant advance! You're close to proving not only that $\mathcal{CH}$ is closed under the inverse operation, but the stronger claim that $\mathcal{C}^{(k)}$ is closed under the inverse operation! This is certainly worth the award. Though please update if you make progress on conjecture 3 which, I agree, sounds very reasonable. Feb 18 at 20:35