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

Polynomial-Time Tolerant Testing Stabilizer States

Srinivasan Arunachalam, Arkopal Dutt

Published Jun 15, 2025• 4 citations
arXivHTMLPDF

Abstract

We consider the following task: suppose an algorithm is given copies of an unknown $n$-qubit quantum state $|ψ\rangle$ promised $(i)$ $|ψ\rangle$ is $\varepsilon_1$-close to a stabilizer state in fidelity or $(ii)$ $|ψ\rangle$ is $\varepsilon_2$-far from all stabilizer states, decide which is the case. We show that for every $\varepsilon_1>0$ and $\varepsilon_2\leq \varepsilon_1^C$, there is a $\textsf{poly}(1/\varepsilon_1)$-sample and $n\cdot \textsf{poly}(1/\varepsilon_1)$-time algorithm that decides which is the case (where $C>1$ is a universal constant). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of quantum states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive combinatorics.

DOI
10.1145/3717823.3718277

Related papers

A note on polynomial-time tolerant testing stabilizer states

Srinivasan Arunachalam, Sergey B. Bravyi, Arkopal Dutt

We show an improved inverse theorem for the Gowers-$3$ norm of $n$-qubit quantum states $|ψ\rangle$ which states that: for every $γ\geq 0$, if the $\textsf{Gowers}(|ψ\rangle,3)^8 \geq γ$ then the stabilizer fidelity of $|ψ\rangle$ is at least $γ^C$ for some constant $C>1$. This implies a constant-sample polynomial-time tolerant testing algorithm for stabilizer states which accepts if an unknown state is $\varepsilon_1$-close to a stabilizer state in fidelity and rejects when $|ψ\rangle$ is $\varepsilon_2 \leq \varepsilon_1^C$-far from all stabilizer states, promised one of them is the case.

arXiv:2410.22220•Oct 29, 2024•0 citations

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

Sample-optimal learning of stabilizer states

Rebecca Chang, Matthias C. Caro, Martin Larocca +1 more

It is well-known that learning a pure $n$-qubit stabilizer state $|ψ\rangle$ both requires, and can be accomplished with, access to a number of copies of $|ψ\rangle$ linear in $n$. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that $L_δ(n)$, the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most $0<δ<1/8$, satisfies $n+\lceil\log_2(1/δ)\rceil-3\leq L_δ(n)\leq n+\left\lceil\log_2(1/δ)\right\rceil+4$. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown $n$-qubit Clifford unitary from $2n+\left\lceil\log_2(1/δ)\right\rceil+4$ queries, the $n$-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group $\mathbb{Z}_4^n \times \mathbb{F}_2^{n(n-1)/2}$, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.

quant-pharXiv:2609.10974•Sep 11, 2026•0 citations

Optimal Stabilizer Testing and Learning with Limited Quantum Memory

Srinivasan Arunachalam, Louis Schatzki

We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown $n$-qubit state, but may keep only $k$ qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test $n$-qubit stabilizer states using $6$ copies, which is dimension independent, unlike the learning complexity of $Θ(n)$. We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that (1) The sample complexity of testing stabilizer states in the $k$-qubit memory framework is $Θ(n-k)$. Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group. (2) The sample complexity of learning stabilizer states with $k$ qubits of memory, in the non-adaptive framework, is $Θ(n^2/k)$. As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with $k=0.99n$ qubits of memory, there is no constant-copy stabilizer tester; furthermore for $k=cn$ qubits of memory (for $0< c < 1$), stabilizer testing is as hard as learning, with both requiring $Θ(n)$ copies.

quant-pharXiv:2607.02444•Jul 3, 2026•0 citations

Learning Stabilizer Structure of Quantum States

Srinivasan Arunachalam, Arkopal Dutt

We consider the task of learning a structured stabilizer decomposition of an arbitrary n-qubit quantum state |ψ⟩: for every ε > 0, output a succinctly describable state |φ⟩ with stabilizer-rank poly(1/ε) such that |ψ⟩=|φ⟩+|φ′⟩ where |φ′⟩ has stabilizer fidelity at most ε. We firstly show the existence of such decompositions using the inverse theorem for the Gowers-3 norm of quantum states that was recently established by our prior work [AD, STOC’25].

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

Improved Bounds for Testing Low Stabilizer Complexity States

Saeed Adel Mehraban, Mehrdad Tahmasbi

Stabilizer states are fundamental families of quantum states with crucial applications such as error correction, quantum computation, and simulation of quantum circuits. In this paper, we study the problem of testing how close or far a quantum state is to a stabilizer state. We make two contributions: First, we improve the state-of-the-art parameters for the tolerant testing of stabilizer states. In particular, we show that there is an efficient quantum primitive to distinguish if the maximum fidelity of a quantum state with a stabilizer state is $\geq ε_1$ or $\leq ε_2$, given one of them is the case, provided that $ε_2 \leq ε_1^{O(1)}$. This result improves the parameters in the previous work [AD24] which assumed $ε_2 \leq e^{- 1/ε^{O(1)}_1}$ [AD24]. Our proof technique extends the toolsets developed in [AD24] by applying a random Clifford map which balances the characteristic function of a quantum state, enabling the use of standard proof techniques from higher-order Fourier analysis for Boolean functions [HHL19, Sam07], where improved testing bounds are available. Second, we study the problem of testing low stabilizer rank states. We show that if for an infinite family of quantum states stabilizer rank is lower than a constant independent of system size, then stabilizer fidelity is lower bounded by an absolute constant. Using a result of [GIKL22], one of the implications of this result is that low approximate stabilizer rank states are not pseudo-random. At the same time our work was completed and posted on arXiv, two other groups [BvDH24, ABD24] independently achieved similar exponential to polynomial improvements for tolerant testing, each using a different approach.

arXiv:2410.24202•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•1 citation
We consider the following task: suppose an algorithm is given copies of an unknown nnn-qubit quantum state ∣ψ⟩|ψ\rangle∣ψ⟩ promised (i)(i)(i) ∣ψ⟩|ψ\rangle∣ψ⟩ is ε1\varepsilon_1ε1​-close to a stabilizer state in fidelity or (ii)(ii)(ii) ∣ψ⟩|ψ\rangle∣ψ⟩ is ε2\varepsilon_2ε2​-far from all stabilizer states, decide which is the case. We show that for every ε1>0\varepsilon_1>0ε1​>0 and ε2≤ε1C\varepsilon_2\leq \varepsilon_1^Cε2​≤ε1C​, there is a poly(1/ε1)\textsf{poly}(1/\varepsilon_1)poly(1/ε1​)-sample and n⋅poly(1/ε1)n\cdot \textsf{poly}(1/\varepsilon_1)n⋅poly(1/ε1​)-time algorithm that decides which is the case (where C>1C>1C>1 is a universal constant). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-333 norm of quantum states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive combinatorics.
We show an improved inverse theorem for the Gowers-333 norm of nnn-qubit quantum states ∣ψ⟩|ψ\rangle∣ψ⟩ which states that: for every γ≥0γ\geq 0γ≥0, if the Gowers(∣ψ⟩,3)8≥γ\textsf{Gowers}(|ψ\rangle,3)^8 \geq γGowers(∣ψ⟩,3)8≥γ then the stabilizer fidelity of ∣ψ⟩|ψ\rangle∣ψ⟩ is at least γCγ^CγC for some constant C>1C>1C>1. This implies a constant-sample polynomial-time tolerant testing algorithm for stabilizer states which accepts if an unknown state is ε1\varepsilon_1ε1​-close to a stabilizer state in fidelity and rejects when ∣ψ⟩|ψ\rangle∣ψ⟩ is ε2≤ε1C\varepsilon_2 \leq \varepsilon_1^Cε2​≤ε1C​-far from all stabilizer states, promised one of them is the case.
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.
It is well-known that learning a pure nnn-qubit stabilizer state ∣ψ⟩|ψ\rangle∣ψ⟩ both requires, and can be accomplished with, access to a number of copies of ∣ψ⟩|ψ\rangle∣ψ⟩ linear in nnn. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that Lδ(n)L_δ(n)Lδ​(n), the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most 0<δ<1/80<δ<1/80<δ<1/8, satisfies n+⌈log⁡2(1/δ)⌉−3≤Lδ(n)≤n+⌈log⁡2(1/δ)⌉+4n+\lceil\log_2(1/δ)\rceil-3\leq L_δ(n)\leq n+\left\lceil\log_2(1/δ)\right\rceil+4n+⌈log2​(1/δ)⌉−3≤Lδ​(n)≤n+⌈log2​(1/δ)⌉+4. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown nnn-qubit Clifford unitary from 2n+⌈log⁡2(1/δ)⌉+42n+\left\lceil\log_2(1/δ)\right\rceil+42n+⌈log2​(1/δ)⌉+4 queries, the nnn-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group Z4n×F2n(n−1)/2\mathbb{Z}_4^n \times \mathbb{F}_2^{n(n-1)/2}Z4n​×F2n(n−1)/2​, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.
We study stabilizer state testing and learning with limited coherent quantum memory. Here an algorithm sequentially receives copies of an unknown nnn-qubit state, but may keep only kkk qubits of coherent quantum memory between measurements. With unrestricted memory, seminal work of Gross, Nezami and Walter showed how to test nnn-qubit stabilizer states using 666 copies, which is dimension independent, unlike the learning complexity of Θ(n)Θ(n)Θ(n). We show that this testing-vs-learning separation is lost under memory constraints. More concretely we show that (1) The sample complexity of testing stabilizer states in the kkk-qubit memory framework is Θ(n−k)Θ(n-k)Θ(n−k). Our upper bound goes via a novel connection to the hidden shift problem and the lower bound is proven using a novel approach to average case bounds on likelihood ratios via combinatorics of the stochastic orthogonal group. (2) The sample complexity of learning stabilizer states with kkk qubits of memory, in the non-adaptive framework, is Θ(n2/k)Θ(n^2/k)Θ(n2/k). As a further application of our techniques, we prove an exponential lower bound for purity testing even when the memory may be left coherent throughout the protocol. Our main results identify coherent quantum memory as the resource enabling the usual separation between stabilizer testing and learning. In particular, even with k=0.99nk=0.99nk=0.99n qubits of memory, there is no constant-copy stabilizer tester; furthermore for k=cnk=cnk=cn qubits of memory (for 0<c<10< c < 10<c<1), stabilizer testing is as hard as learning, with both requiring Θ(n)Θ(n)Θ(n) copies.
Stabilizer states are fundamental families of quantum states with crucial applications such as error correction, quantum computation, and simulation of quantum circuits. In this paper, we study the problem of testing how close or far a quantum state is to a stabilizer state. We make two contributions: First, we improve the state-of-the-art parameters for the tolerant testing of stabilizer states. In particular, we show that there is an efficient quantum primitive to distinguish if the maximum fidelity of a quantum state with a stabilizer state is ≥ε1\geq ε_1≥ε1​ or ≤ε2\leq ε_2≤ε2​, given one of them is the case, provided that ε2≤ε1O(1)ε_2 \leq ε_1^{O(1)}ε2​≤ε1O(1)​. This result improves the parameters in the previous work [AD24] which assumed ε2≤e−1/ε1O(1)ε_2 \leq e^{- 1/ε^{O(1)}_1}ε2​≤e−1/ε1O(1)​ [AD24]. Our proof technique extends the toolsets developed in [AD24] by applying a random Clifford map which balances the characteristic function of a quantum state, enabling the use of standard proof techniques from higher-order Fourier analysis for Boolean functions [HHL19, Sam07], where improved testing bounds are available. Second, we study the problem of testing low stabilizer rank states. We show that if for an infinite family of quantum states stabilizer rank is lower than a constant independent of system size, then stabilizer fidelity is lower bounded by an absolute constant. Using a result of [GIKL22], one of the implications of this result is that low approximate stabilizer rank states are not pseudo-random. At the same time our work was completed and posted on arXiv, two other groups [BvDH24, ABD24] independently achieved similar exponential to polynomial improvements for tolerant testing, each using a different approach.