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:2510.07164 · ACM Symposium on Theory of Computing (STOC)

Clifford Testing: Algorithms and Lower Bounds

Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert, Jop Briët, Jonas Helsen

Published Jun 9, 2026• 5 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1145/3798129.3800801

Related papers

Single-Copy Stabilizer Testing

Marcel Hinsche, Jonas Helsen

We consider the problem of testing whether an unknown n-qubit quantum state is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n) copies, and conversely prove that Ω(√n) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.

•Jan 1, 2025•0 citations

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

Zongbo, Bao, Jop Briët +3 more

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.

quant-pharXiv:2605.26983•May 27, 2026•4 citations

Single-Copy Stabilizer Testing

Marcel Hinsche, Jonas Helsen

We consider the problem of testing whether an unknown $n$-qubit quantum state $|ψ\rangle$ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using $O(n)$ copies, and conversely prove that $Ω(\sqrt{n})$ copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.

arXiv:2410.07986•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•18 citations

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•8 citations

Quantum Advantage in Tolerant Junta Testing

Avishay Tal, Weiqiang Yuan

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

cs.CCCross-listedarXiv:2606.23194•Leibniz international proceedings in informatics•Jun 23, 2026•1 citation

Adaptivity is all you need: Optimal stabilizer learning using just single-copy measurements

L. Bittel, J. Eisert, W. Gong +2 more

Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an $n$-qubit stabilizer state can be learned from $Θ(n)$ copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require $Ω(n^2)$ copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary $n$-qubit stabilizer state from $Θ(n)$ single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with $k$ qubits of quantum memory, the optimal testing tradeoff $Θ(n-k+1/\varepsilon)$ at infidelity $\varepsilon$. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most $r$, including states prepared by Clifford circuits with a bounded number of $T$ gates, can be learned using $O(n2^{r})$ single-copy measurements.

quant-pharXiv:2610.02031•Oct 2, 2026•1 citation
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.
We consider the problem of testing whether an unknown n-qubit quantum state is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n) copies, and conversely prove that Ω(√n) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.
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 consider the problem of testing whether an unknown nnn-qubit quantum state ∣ψ⟩|ψ\rangle∣ψ⟩ is a stabilizer state, with only single-copy access. We give an algorithm solving this problem using O(n)O(n)O(n) copies, and conversely prove that Ω(n)Ω(\sqrt{n})Ω(n​) copies are required for any algorithm. The main observation behind our algorithm is that when repeatedly measuring in a randomly chosen stabilizer basis, stabilizer states are the most likely among the set of all pure states to exhibit linear dependencies in measurement outcomes. Our algorithm is designed to probe deviations from this extremal behavior. For the lower bound, we first reduce stabilizer testing to the task of distinguishing random stabilizer states from the maximally mixed state. We then argue that, without loss of generality, it is sufficient to consider measurement strategies that a) lie in the commutant of the tensor action of the Clifford group and b) satisfy a Positive Partial Transpose (PPT) condition. By leveraging these constraints, together with novel results on the partial transposes of the generators of the Clifford commutant, we derive the lower bound on the sample complexity.
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.
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant kkk-junta testing with high precision can be solved using poly(k)\mathrm{poly}(k)poly(k) quantum queries, whereas any classical algorithm requires at least kΩ(log⁡k)k^{Ω(\log k)}kΩ(logk) queries. The problem of tolerant kkk-junta testing is as follows: given parameters (k,ε1,ε2)(k, ε_1, ε_2)(k,ε1​,ε2​), with 0≤ε1<ε2≤1/20\le ε_1<ε_2 \le 1/20≤ε1​<ε2​≤1/2, and black-box access to a Boolean function fff (defined on nnn variables), distinguish whether fff is ε1ε_1ε1​-close to some kkk-junta or ε2ε_2ε2​-far from every kkk-junta. We show the quantum advantage for a range of parameters close to 1/21/21/2, for example, ε1=1/2−1/kε_1 = 1/2-1/kε1​=1/2−1/k and ε2=1/2−1/(2k2)ε_2 = 1/2-1/(2k^2)ε2​=1/2−1/(2k2). The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most ε1ε_1ε1​ to kkk-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick kkk out of nnn coordinates, and for each fixing of the kkk coordinates, the 2n−k2^{n-k}2n−k values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to kkk-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making ko(log⁡k)k^{o(\log k)}ko(logk) queries.
Stabilizer states are central to quantum computing, underlying quantum error correction, benchmarking, and efficient classical simulation. Yet their learnability exhibits a striking gap: an nnn-qubit stabilizer state can be learned from Θ(n)Θ(n)Θ(n) copies using two-copy Bell measurements, whereas non-adaptive single-copy measurements require Ω(n2)Ω(n^2)Ω(n2) copies. Here we show that adaptivity completely closes this gap. We give a polynomial-time adaptive algorithm that learns an arbitrary nnn-qubit stabilizer state from Θ(n)Θ(n)Θ(n) single-copy Clifford measurements, matching the optimal sample complexity of Bell sampling without any multi-copy measurements. The same ideas yield a sample-optimal single-copy tolerant tester and, with kkk qubits of quantum memory, the optimal testing tradeoff Θ(n−k+1/ε)Θ(n-k+1/\varepsilon)Θ(n−k+1/ε) at infidelity ε\varepsilonε. Finally, we show that this adaptive mechanism extends beyond exact stabilizer states: states of stabilizer nullity at most rrr, including states prepared by Clifford circuits with a bounded number of TTT gates, can be learned using O(n2r)O(n2^{r})O(n2r) single-copy measurements.