arXiv:2610.06402
When is the Clifford hierarchy generalized semi-Clifford?
Rongbiao Thomas Wang, Bobby Zixuan Zhang
Abstract
We study semi-Clifford and generalized semi-Clifford structures in the Clifford hierarchy as a function of hierarchy level $k$ and qubit number $n$. We show that $\mathcal{C}_k(n)$ is semi-Clifford if and only if $k\le2$, $n\le2$, or $k=3$ and $n\le6$. We also establish that $\mathcal{C}_k(n)$ is generalized semi-Clifford when $k\le4$ or $n\le3$ and construct counterexamples when $k,n \geq 5$. For $n=4$ and $k\ge5$, we show that every gate defined over $\mathbb{Q}(i)$ up to a scalar is generalized semi-Clifford, reduce the general case to a single level, and propose a strategy to prove our conjecture that $\mathcal{C}_k(n)$ is generalized semi-Clifford if and only if $k\le4$ or $n\le4$. Lastly, we go beyond this structure by introducing $n_c$-generalized semi-Clifford gates, which we show are exactly the gates of the form $\sum_x|π(x)\rangle\langle x|\otimes V_x$ up to Clifford gates on both sides, where $π$ permutes the computational basis states of $n_c$ control qubits. We conjecture that for $k\ge3$ every gate in $\mathcal{C}_k(n)$ has this form for some $n_c\ge1$ with every $V_x\in\mathcal{C}_{k-3}(n-n_c)$, refining the conjecture of Zeng, Chen, and Chuang.
AI Summary
The paper asks when every gate in a Clifford-hierarchy level admits a semi-Clifford (SC) or generalized semi-Clifford (GSC) decomposition: Clifford-equivalent to a diagonal or monomial gate, respectively. It completes the SC boundary: $\mathcal C_k(n)\subseteq\mathsf{SC}(n)$ exactly when $k\le2$, $n\le2$, or $k=3$ with $n\le6$. The new positive cases are five- and six-qubit third-level gates. For GSC structure, it proves inclusion for all widths at $k\le4$ and all levels at $n\le3$, and constructs non-GSC gates of exact level $k$ for every $k,n\ge5$. The fourth-level inclusion was also obtained independently elsewhere; a five-qubit fifth-level counterexample was already known. The fourth-level proof uses finite $2$-groups generated by Paulis and their conjugates, together with parity arguments yielding an invariant Pauli maximal abelian algebra. Small-width proofs combine symplectic reductions, exact finite computational checks, and descent in the smallest dyadic cyclotomic field defining a gate up to scalar. Four qubits at levels $k\ge5$ remain unresolved. Gates defined over $\mathbb Q(i)$ up to scalar are proved GSC, and the general question reduces to checking level $4290$, still computationally impractical. The paper also characterizes partial GSC structure through Clifford-equivalent controlled-block decompositions and conjectures that every level-$k$ gate has such a decomposition with at least one control and blocks in $\mathcal C_{k-3}$.
We have also used the LLMs to help with the writing and polishing of the paper.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 50 pages, 13 figures, 1 table