8
$\begingroup$

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}$?


Cases:

$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}$.
$\endgroup$
10
  • $\begingroup$ +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 $\endgroup$ Feb 8 at 18:25
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 8 at 18:38
  • $\begingroup$ 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? $\endgroup$ Feb 8 at 18:42
  • $\begingroup$ 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. $\endgroup$ Feb 10 at 4:56
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 14 at 21:40

1 Answer 1

3
$\begingroup$

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

enter image description here

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.$$

$\endgroup$
2
  • $\begingroup$ oh dang sorry the bounty expired, I would have totally awarded it to you, this answer looks really fun! $\endgroup$ Feb 18 at 1:13
  • $\begingroup$ 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. $\endgroup$ Feb 18 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.