Highest Clifford-hierarchy level of controlled gates with higher-level targets

Unsolved ID op_e432fc5ff73e63be Last edited 15 September 2026

Edit

Field: Quantum Algorithm
Topic: Clifford hierarchy

Problem

What is the highest Clifford-hierarchy level that a controlled gate can reach when its target lies in a given level \(k\geq3\) and has a given Pauli periodicity, and is that level bounded independently of the number of target qubits? Let \(n\geq1\), and let \(\mathcal P_n\) be the \(n\)-qubit Pauli group, consisting of the operators \(\omega P_1\otimes\cdots\otimes P_n\) with \(\omega\in\{\pm1,\pm i\}\) and \(P_j\in\{I,X,Y,Z\}\). The Clifford hierarchy is defined by

\begin{equation} \mathcal C_1(n):=\mathcal P_n, \qquad \mathcal C_{k+1}(n):=\bigl\{U\in U(2^n):UPU^\dagger\in\mathcal C_k(n) \ \text{for every}\ P\in\mathcal P_n\bigr\}, \qquad k\geq1. \tag{1} \end{equation}

Write \(\mathcal C_\infty(n):=\bigcup_{k\geq1}\mathcal C_k(n)\), and let \(\ell_n(V):=\min\{k\geq1:V\in\mathcal C_k(n)\}\) be the exact level of \(V\in\mathcal C_\infty(n)\). For \(U\in U(2^n)\), define the controlled gate and the Pauli periodicity

\begin{equation} CU:=|0\rangle\langle0|\otimes I+|1\rangle\langle1|\otimes U\in U(2^{n+1}), \qquad m(U):=\min\bigl\{t\in\mathbb Z_{\geq0}:U^{2^t}\in\mathcal P_n\bigr\}, \tag{2} \end{equation}

with \(m(U):=\infty\) when no such \(t\) exists. Only the four phases \(\pm1,\pm i\) count as Pauli phases in Eqs. (1) and (2). This convention is essential: replacing \(U\) by \(e^{i\theta}U\) multiplies \(CU\) by a phase gate on the control qubit, and it can change both \(m(U)\) and the level of \(CU\).

For integers \(k\geq2\) and \(m\geq0\), the highest level reachable by controlling a \(k\)th-level target with Pauli periodicity \(m\) is

\begin{equation} L(n,k,m):=\max\bigl\{\ell_{n+1}(CU): U\in\mathcal C_k(n),\ m(U)=m,\ CU\in\mathcal C_\infty(n+1)\bigr\}. \tag{3} \end{equation}

The set in Eq. (3) is nonempty because \(U=e^{i\pi/2^{m+1}}I\) qualifies, and the maximum is attained because \(\mathcal C_k(n)\) is finite modulo global phase while fixing \(m(U)\) leaves finitely many admissible phases. Membership \(U\in\mathcal C_k(n)\) includes the lower levels, so \(L(n,k,m)\) is nondecreasing in \(k\). Determine \(L(n,k,m)\) for all \(n\geq1\), \(k\geq3\), and \(m\geq0\). In particular, is \(L(n,k,m)\) bounded by a function of \(k\) and \(m\) alone, independently of the number \(n\) of target qubits?

Source

Xu and Wang pose the question explicitly as Open Problem 1 in Section 5: among all \(n\)-qubit unitaries in the \(k\)th level of the hierarchy with Pauli periodicity \(m\), what is the highest level that the controlled gate can reach? They note that the answer can depend simultaneously on \(m\), \(n\), and \(k\), and that controlling non-Clifford targets could potentially bypass the exponential qubit overhead inherent to Clifford targets [XW26]. This record makes the discrete phase convention of their Definition 4 and the requirement \(CU\in\mathcal C_\infty(n+1)\) explicit, and states the dependence on \(n\) as a boundedness question.

Progress

Clifford targets are settled. Xu and Wang proved the controlled-jump criterion (Theorem 3): every Clifford gate \(U\notin\{\pm I\}\) with \(m(U)<\infty\) satisfies

\begin{equation} CU\in\mathcal C_{m(U)+2}(n+1)\setminus\mathcal C_{m(U)+1}(n+1) \tag{4} \end{equation}

[XW26]. Their theorem is stated for all Clifford targets; the two excluded gates, for which \(CU\) is a Pauli operator, matter only when \(m(U)=0\). For non-Pauli targets, Lemma 1 of Surti, Daguerre, and Kim had characterized the third level: \(CU\in\mathcal C_3(n+1)\) exactly when \(U\) is a Clifford gate with \(U^2\in\mathcal P_n\) [SDK26]. Because \(e^{i\pi/2^{m+1}}I\) is a Clifford gate with Pauli periodicity \(m\), Eq. (4) gives \(L(n,2,m)=m+2\) for all \(n\geq1\) and \(m\geq0\).
The qubit count enters only after the global phase is discarded. Theorem 4 of Xu and Wang bounds the Pauli periodicity of an \(n\)-qubit Clifford gate by \(\lceil\log_2(2n)\rceil\), and their Corollary 1 converts this into the requirement \(n\geq2^{k-4}+1\) for a Clifford target whose controlled gate lies exactly in level \(k\geq4\) [XW26]. The proof bounds the order of the binary symplectic matrix of \(U\), which ignores the global phase, whereas their Definition 4 of Pauli periodicity, like Eq. (2), admits only the phases \(\pm1,\pm i\). Under that convention the bound fails as literally stated: \(U=e^{i\pi/16}I\) is a one-qubit Clifford gate with \(m(U)=3>\lceil\log_2 2\rceil\), and \(CU=\operatorname{diag}(1,e^{i\pi/16})\otimes I\) lies exactly in level \(5\) on two qubits, in agreement with Eq. (4). The qubit-count bounds therefore hold for phase-normalized Clifford targets, whose global phase is chosen to minimize \(m(U)\). This caveat is a deduction made for this record, not a statement of the source.
Every target obeys three lower bounds. The repeated-commutator argument of Anderson and Weippert (Theorem 2.4 and Corollary 2.4.1), reproduced as the proof of Theorem 1 by Xu and Wang, uses no Clifford assumption: \(CU\in\mathcal C_r(n+1)\) with \(r\geq2\) forces \(U^{2^{r-2}}\in\mathcal P_n\) [AW24], [XW26]. Separately, a direct calculation gives

\begin{equation} CU\,(X\otimes I)\,CU^\dagger =(X\otimes I)\bigl(|0\rangle\langle0|\otimes U +|1\rangle\langle1|\otimes U^\dagger\bigr), \tag{5} \end{equation}

and the block-diagonal lemma of Xu and Wang (Lemma 2) then places both \(U\) and \(U^\dagger\) one level below \(CU\). Consequently, whenever \(U\notin\{\pm I\}\) and \(CU\in\mathcal C_\infty(n+1)\), the gates \(U\) and \(U^\dagger\) lie in the hierarchy and

\begin{equation} \ell_{n+1}(CU)\geq\max\bigl\{m(U)+2,\ \ell_n(U)+1,\ \ell_n(U^\dagger)+1\bigr\}. \tag{6} \end{equation}

The first term is the source argument; the second and third, obtained from Eq. (5), are deductions made for this record.
Non-Clifford targets already break the Clifford formula. The classification of diagonal gates in the hierarchy (Theorem 3 of Cui, Gottesman, and Krishna), together with Eq. (6), gives the exact levels, for \(k\geq2\),

\begin{equation} \begin{aligned} &U=C^{k-1}Z: && \ell_k(U)=k, && m(U)=1, && \ell_{k+1}(CU)=k+1;\\ &U=\operatorname{diag}\bigl(1,e^{i\pi/2^{k-1}}\bigr): && \ell_1(U)=k, && m(U)=k-1, && \ell_2(CU)=k+1, \end{aligned} \tag{7} \end{equation}

where \(C^{k-1}Z\) is the \(k\)-qubit multi-controlled \(Z\) gate [CGK17]. The first family in Eq. (7) exceeds \(m(U)+2\) when \(k\geq3\), and in both families the control raises the level by exactly one. Anderson and Weippert (Section 3) ask whether this always happens, that is, whether \(U\in\mathcal C_k\setminus\mathcal C_{k-1}\) implies \(CU\in\mathcal C_{k+1}\setminus\mathcal C_k\) [AW24]. Clifford targets already answer negatively: the three-qubit CNOT string whose linear part is a single Jordan block is a Clifford permutation with \(m(U)=2\) by Corollary 2 of Xu and Wang, so \(\ell_3(U)=2\) while \(\ell_4(CU)=4\) by Eq. (4) [XW26].
Third-level targets either leave the hierarchy under control or gain at least \(k-1\) levels. He, Robitaille, and Tan construct, for every \(k\geq3\), a permutation gate \(U_k\) on \(2^k-1\) qubits with

\begin{equation} U_k\in\mathcal C_3(2^k-1), \qquad U_k^{-1}\notin\mathcal C_k(2^k-1) \tag{8} \end{equation}

(Theorem 5.4 of the arXiv version, Theorem 42 of the proceedings version) [HRT26]. By Eqs. (6) and (8), either \(CU_k\notin\mathcal C_\infty(2^k)\) or \(\ell_{2^k}(CU_k)\geq k+2\); neither alternative is established in the sources located. If the second alternative holds for infinitely many \(k\) along which \(m(U_k)\) stays bounded, then \(L(n,3,m)\) is unbounded in \(n\) for some \(m\), which answers the second question negatively. The sources do not determine \(m(U_k)\). A direct computation for this record from the Toffoli-circuit form of \(U_k\) (Proposition 5.2 of the arXiv version) gives \(m(U_3)=m(U_4)=2\), whereas \(U_6^4\) is a nonidentity permutation fixing \(|0\cdots0\rangle\), hence not a Pauli operator, so \(m(U_6)\geq3\). The dichotomy and these values are deductions made for this record.
The condition \(CU\in\mathcal C_\infty(n+1)\) in Eq. (3) cannot be dropped. Anderson and Weippert (Corollary 2.4.1) show that \(CU\in\mathcal C_\infty(n+1)\) requires \(U\in\mathcal C_\infty(n)\) and \(m(U)<\infty\), and their Section 3 leaves sufficiency open [AW24]. De Silva and Lautsch give the explicit five-qubit gate \(U=\operatorname{ctrl}_c(B)\operatorname{ctrl}_d(A)\), with control qubits \(c,d\) and three-qubit Clifford targets \(A=CX_{2\to3}CZ_{2,3}\) and \(B=CX_{2\to3}CX_{1\to2}H_1\), and prove

\begin{equation} U\in\mathcal C_5(5)\setminus\mathcal C_4(5), \qquad U^\dagger\notin\mathcal C_\infty(5) \tag{9} \end{equation}

(Theorems 8.1 and 8.2 of their September 2026 preliminary preprint; their first level admits all global phases, which leaves every level \(k\geq2\) unchanged) [dSL26]. A direct matrix computation for this record gives \(U^8=I\) and \(U^4\notin\mathcal P_5\), so \(m(U)=3\); Eqs. (6) and (9) then give \(CU\notin\mathcal C_\infty(6)\). Thus hierarchy membership and finite Pauli periodicity of the target do not suffice.

Comment

This is Open Problem 1 of Xu and Wang, with the phase convention and the hierarchy-membership condition made explicit [XW26]. No determination of \(L(n,k,m)\) for \(k\geq3\) and no upper bound on the level of a controlled gate with a non-Clifford target was located, and the works located that cite Xu and Wang do not address it. The Clifford rule in Eq. (4), the diagonal families in Eq. (7), and the lower bounds in Eq. (6) constrain \(L(n,k,m)\) only from below. A complete answer requires matching upper bounds on \(\ell_{n+1}(CU)\) for targets in \(\mathcal C_k(n)\) with \(k\geq3\); a negative answer to the boundedness question requires targets with fixed \(k\) and \(m\) whose controlled gates lie in the hierarchy at levels unbounded in \(n\). Literature checked through 15 September 2026.

References

[XW26]: Y. Xu and X. Wang, “Controlled jump in the Clifford hierarchy,” arXiv:2602.22201 (2026).DOI arXiv
[AW24]: J. T. Anderson and M. Weippert, “Controlled gates in the Clifford hierarchy,” arXiv:2410.04711 (2024), version 3 (2025).DOI arXiv
[SDK26]: S. Surti, L. Daguerre, and I. H. Kim, “Efficient Simulation of Logical Magic State Preparation Protocols,” PRX Quantum 7, 020329 (2026).DOI arXiv
[CGK17]: S. X. Cui, D. Gottesman, and A. Krishna, “Diagonal gates in the Clifford hierarchy,” Physical Review A 95, 012329 (2017).DOI arXiv
[HRT26]: Z. He, L. Robitaille, and X. Tan, “Characterization of Permutation Gates in the Third Level of the Clifford Hierarchy,” in 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026), LIPIcs 389, 2:1–2:17 (2026).DOI arXiv
[dSL26]: N. de Silva and O. Lautsch, “The generalised semi-Clifford conjecture is false,” arXiv:2609.11903 (2026), preliminary draft.DOI arXiv

Highest Clifford-hierarchy level of controlled gates with higher-level targets

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems