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:2410.22220

A note on polynomial-time tolerant testing stabilizer states

Srinivasan Arunachalam, Sergey B. Bravyi, Arkopal Dutt

Published Oct 29, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2410.22220

Related papers

Polynomial-Time Tolerant Testing Stabilizer States

Srinivasan Arunachalam, Arkopal Dutt

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.

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

Tolerant Testing of Stabilizer States with Mixed State Inputs

Vishnu Iyer, Daniel Liang

We study the problem of tolerant testing of stabilizer states. In particular, we give the first such algorithm that accepts mixed state inputs. Formally, given a mixed state $ρ$ that either has fidelity at least $\varepsilon_1$ with some stabilizer pure state or fidelity at most $\varepsilon_2$ with all such states, where $\varepsilon_2 \leq \varepsilon_1^{O(1)}$, our algorithm distinguishes the two cases with sample complexity $\text{poly}(1/\varepsilon_1)$ and time complexity $O(n \cdot \text{poly}(1/\varepsilon_1))$.

arXiv:2411.08765•Nov 13, 2024•1 citation

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

Agnostic learning of qudit stabilizer states

Wentao Qi, Boyan Xu, Shiguang Feng +1 more

Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown $n$-qudit pure state $|ψ\rangle$ that has fidelity $τ$ with some stabilizer state, our algorithm outputs a stabilizer state $|φ\rangle$ such that $\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon$ with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as $(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)$, where the dimension $d$ is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime $τ> \cos^2(π/8)$, establishing a qudit analogue of the threshold-based approach in prior qubit work.

quant-pharXiv:2607.15559•Jul 20, 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

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
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 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 study the problem of tolerant testing of stabilizer states. In particular, we give the first such algorithm that accepts mixed state inputs. Formally, given a mixed state ρρρ that either has fidelity at least ε1\varepsilon_1ε1​ with some stabilizer pure state or fidelity at most ε2\varepsilon_2ε2​ with all such states, where ε2≤ε1O(1)\varepsilon_2 \leq \varepsilon_1^{O(1)}ε2​≤ε1O(1)​, our algorithm distinguishes the two cases with sample complexity poly(1/ε1)\text{poly}(1/\varepsilon_1)poly(1/ε1​) and time complexity O(n⋅poly(1/ε1))O(n \cdot \text{poly}(1/\varepsilon_1))O(n⋅poly(1/ε1​)).
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.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown nnn-qudit pure state ∣ψ⟩|ψ\rangle∣ψ⟩ that has fidelity τττ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩|φ\rangle∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log⁡(1/τ))⋅poly(n,1/ε)(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)(d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension ddd is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos⁡2(π/8)τ> \cos^2(π/8)τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
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.