Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.26983

On Clifford hierarchy testing and near-extremizers of noncommutative uniformity norms

Zongbo, Bao, Jop Briët, Davi Castro-Silva, Philippe van Dordrecht, Jonas Helsen

quant-phSubmitted May 26, 2026• Announced May 27, 2026• 0 citations
arXivHTMLPDF

Abstract

We consider the problem of testing whether an unknown unitary is close to a specified level of the Clifford hierarchy. Bu, Gu, and Jaffe proposed a candidate tester for this task based on a connection with noncommutative analogues of the Gowers uniformity norms. The complexity of this tester -- whose analysis depends on a robust characterization of the near-extremizers of these norms -- was left open. We establish such a characterization for the fourth noncommutative uniformity norm and, as a consequence, obtain an efficient tester for the third level of the Clifford hierarchy. We further discuss possible routes toward resolving the problem of testing for all higher levels, highlighting the main barriers that remain.

Comments
17 pages, 99% inverse theorem for Gowers norm for unitaries. Comments welcome!

Related papers

Norm properties of quantum uniformity measures

Berke Ünal

We give a complete classification of the norm properties of quantum uniformity measures, introduced by Bu, Gu, and Jaffe to analytically characterize the Clifford hierarchy. Resolving an open question they posed, we show that quantum uniformity measures define norms precisely for $k=2,3,4$. In particular, we establish the triangle inequality for $k=4$, whereas for every $k\geq5$ it fails in some dimension. The higher-order result is proved using the structure theory of norming systems of linear equations over finite fields. We also study the geometry of quantum uniformity measures, establishing explicit bounds on the modulus of convexity whenever they define norms. Finally, we give a complete classification of the norm properties of matrix-valued Gowers uniformity functionals, showing that only $k=2$ defines a norm.

math-phCross-listedarXiv:2610.17454•Oct 14, 2026

Clifford Testing: Algorithms and Lower Bounds

Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht +3 more

We consider the problem of Clifford testing, which asks whether a black-box n-qubit unitary is a Clifford unitary or at least ε-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability poly(ε). This contrasts with the minimum of 6 copies required for the closely-related task of stabilizer testing. We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting. In doing so, we settle in the positive a conjecture of Bu, Gu and Jaffe, by proving a polynomial inverse theorem for a non-commutative Gowers 3-uniformity norm. We also consider the restricted setting of single-copy access, where we give an O(n)-query Clifford tester that requires no auxiliary memory qubits or adaptivity. We complement this with a lower bound, proving that any such, potentially adaptive, single-copy algorithm needs at least Ω(n1/4) queries. To obtain our results, we leverage the structure of the commutant of the Clifford group, obtaining several technical statements that may be of independent interest.

arXiv:2510.07164•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•0 citations

A Cohomological Characterization of the Clifford Hierarchy

Junaid Aftab

The Clifford hierarchy plays a central role in fault-tolerant quantum computation, but its higher levels remain only partially understood. Recent work on quantum higher order Fourier analysis characterizes membership in the Clifford hierarchy using quantum derivatives, but does not provide an explicit description of the individual levels. In this work, we address this problem by showing that the collection of quantum derivatives of a unitary operator forms a non-abelian \(1\)-cocycle, and conversely that every such \(1\)-cocycle arises from a unitary operator. This yields a recursive cohomological characterization of the Clifford hierarchy. We then specialize this framework to the third level and decompose the cocycle data into symplectic, affine, and phase components, each admitting a cohomological interpretation. As applications, we give a new proof that every two-qudit gate in the third level of the Clifford hierarchy is semi-Clifford, and prove for the first time that every three-qudit gate in the third level is semi-Clifford.

math-phCross-listedarXiv:2610.06699•Oct 6, 2026•0 citations

Quantum higher-order Fourier analysis and the Clifford hierarchy

Kaifeng Bu, Weichen Gu, Arthur M. Jaffe

We propose a mathematical framework that we call quantum, higher-order Fourier analysis. This generalizes the classical theory of higher-order Fourier analysis, which led to many recent advances in number theory and combinatorics. We define a family of "quantum measures" on linear transformations on a Hilbert space, that reduce in the case of diagonal matrices to the uniformity norms introduced by Timothy Gowers. We show that our quantum measures and our related theory of quantum higher-order Fourier analysis characterize the Clifford hierarchy, an important notion of complexity in quantum computation. In particular, we give a necessary and sufficient analytic condition that a unitary is an element of the [Formula: see text] level of the Clifford hierarchy.

arXiv:2508.15908•Proceedings of the National Academy of Sciences•Nov 7, 2025•1 citation

Tolerant Quantum Junta Testing

Zhaoyang Chen, Lvzhou Li, Jingquan Luo

Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is $ε_1$-close to some quantum $k$-junta or is $ε_2$-far from any quantum $k$-junta, where an $n$-qubit unitary $U$ is called a quantum $k$-junta if it only non-trivially acts on just $k$ of the $n$ qubits. More specifically, we present a tolerant tester with $ε_1 = \frac{\sqrtρ}{8} ε$, $ε_2 = ε$, and $ρ\in (0,1)$, and the query complexity is $O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)$, which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to $U^\dagger$, whereas this is usually required in the literature.

arXiv:2411.02244•Nov 4, 2024•1 citation

Characterization of Permutation Gates in the Third Level of the Clifford Hierarchy

Zhiyang He, Luke Robitaille, Xinyu Tan

The Clifford hierarchy is a fundamental structure in quantum computation whose mathematical properties are not fully understood. In this work, we characterize permutation gates -- unitaries which permute the $2^n$ basis states -- in the third level of the hierarchy. We prove that any permutation gate in the third level must be a product of Toffoli gates in what we define as \emph{staircase form}, up to left and right multiplications by Clifford permutations. We then present necessary and sufficient conditions for a staircase form permutation gate to be in the third level of the Clifford hierarchy. As a corollary, we construct a family of non-semi-Clifford permutation gates $\{U_k\}_{k\geq 3}$ in staircase form such that each $U_k$ is in the third level but its inverse is not in the $k$-th level.

arXiv:2510.04993•Leibniz international proceedings in informatics•Oct 6, 2025•0 citations
We consider the problem of testing whether an unknown unitary is close to a specified level of the Clifford hierarchy. Bu, Gu, and Jaffe proposed a candidate tester for this task based on a connection with noncommutative analogues of the Gowers uniformity norms. The complexity of this tester -- whose analysis depends on a robust characterization of the near-extremizers of these norms -- was left open. We establish such a characterization for the fourth noncommutative uniformity norm and, as a consequence, obtain an efficient tester for the third level of the Clifford hierarchy. We further discuss possible routes toward resolving the problem of testing for all higher levels, highlighting the main barriers that remain.
We give a complete classification of the norm properties of quantum uniformity measures, introduced by Bu, Gu, and Jaffe to analytically characterize the Clifford hierarchy. Resolving an open question they posed, we show that quantum uniformity measures define norms precisely for k=2,3,4k=2,3,4k=2,3,4. In particular, we establish the triangle inequality for k=4k=4k=4, whereas for every k≥5k\geq5k≥5 it fails in some dimension. The higher-order result is proved using the structure theory of norming systems of linear equations over finite fields. We also study the geometry of quantum uniformity measures, establishing explicit bounds on the modulus of convexity whenever they define norms. Finally, we give a complete classification of the norm properties of matrix-valued Gowers uniformity functionals, showing that only k=2k=2k=2 defines a norm.
We consider the problem of Clifford testing, which asks whether a black-box n-qubit unitary is a Clifford unitary or at least ε-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this problem with probability poly(ε). This contrasts with the minimum of 6 copies required for the closely-related task of stabilizer testing. We show that our tester is tolerant, by adapting techniques from tolerant stabilizer testing to our setting. In doing so, we settle in the positive a conjecture of Bu, Gu and Jaffe, by proving a polynomial inverse theorem for a non-commutative Gowers 3-uniformity norm. We also consider the restricted setting of single-copy access, where we give an O(n)-query Clifford tester that requires no auxiliary memory qubits or adaptivity. We complement this with a lower bound, proving that any such, potentially adaptive, single-copy algorithm needs at least Ω(n1/4) queries. To obtain our results, we leverage the structure of the commutant of the Clifford group, obtaining several technical statements that may be of independent interest.
The Clifford hierarchy plays a central role in fault-tolerant quantum computation, but its higher levels remain only partially understood. Recent work on quantum higher order Fourier analysis characterizes membership in the Clifford hierarchy using quantum derivatives, but does not provide an explicit description of the individual levels. In this work, we address this problem by showing that the collection of quantum derivatives of a unitary operator forms a non-abelian 111-cocycle, and conversely that every such 111-cocycle arises from a unitary operator. This yields a recursive cohomological characterization of the Clifford hierarchy. We then specialize this framework to the third level and decompose the cocycle data into symplectic, affine, and phase components, each admitting a cohomological interpretation. As applications, we give a new proof that every two-qudit gate in the third level of the Clifford hierarchy is semi-Clifford, and prove for the first time that every three-qudit gate in the third level is semi-Clifford.
We propose a mathematical framework that we call quantum, higher-order Fourier analysis. This generalizes the classical theory of higher-order Fourier analysis, which led to many recent advances in number theory and combinatorics. We define a family of "quantum measures" on linear transformations on a Hilbert space, that reduce in the case of diagonal matrices to the uniformity norms introduced by Timothy Gowers. We show that our quantum measures and our related theory of quantum higher-order Fourier analysis characterize the Clifford hierarchy, an important notion of complexity in quantum computation. In particular, we give a necessary and sufficient analytic condition that a unitary is an element of the [Formula: see text] level of the Clifford hierarchy.
Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is ε1ε_1ε1​-close to some quantum kkk-junta or is ε2ε_2ε2​-far from any quantum kkk-junta, where an nnn-qubit unitary UUU is called a quantum kkk-junta if it only non-trivially acts on just kkk of the nnn qubits. More specifically, we present a tolerant tester with ε1=ρ8εε_1 = \frac{\sqrtρ}{8} εε1​=8ρ​​ε, ε2=εε_2 = εε2​=ε, and ρ∈(0,1)ρ\in (0,1)ρ∈(0,1), and the query complexity is O(klog⁡kε2ρ(1−ρ)k)O\left(\frac{k \log k}{ε^2 ρ(1-ρ)^k}\right)O(ε2ρ(1−ρ)kklogk​), which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to U†U^\daggerU†, whereas this is usually required in the literature.
The Clifford hierarchy is a fundamental structure in quantum computation whose mathematical properties are not fully understood. In this work, we characterize permutation gates -- unitaries which permute the 2n2^n2n basis states -- in the third level of the hierarchy. We prove that any permutation gate in the third level must be a product of Toffoli gates in what we define as \emph{staircase form}, up to left and right multiplications by Clifford permutations. We then present necessary and sufficient conditions for a staircase form permutation gate to be in the third level of the Clifford hierarchy. As a corollary, we construct a family of non-semi-Clifford permutation gates {Uk}k≥3\{U_k\}_{k\geq 3}{Uk​}k≥3​ in staircase form such that each UkU_kUk​ is in the third level but its inverse is not in the kkk-th level.