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

Agnostic learning of qudit stabilizer states

Wentao Qi, Boyan Xu, Shiguang Feng, Lvzhou Li

quant-phSubmitted Jul 17, 2026• Announced Jul 20, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

Stabilizer Bootstrapping: A Recipe for Efficient Agnostic Tomography and Magic Estimation

Sitan Chen, Weiyuan Gong, Qi Ye +1 more

We study the task of agnostic tomography: given copies of an unknown $n$-qubit state $ρ$ which has fidelity $τ$ with some state in a given class $C$, find a state which has fidelity $\ge τ- ε$ with $ρ$. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: Stabilizer states: We give a protocol that runs in time $\mathrm{poly}(n,1/ε)\cdot (1/τ)^{O(\log(1/τ))}$, answering an open question posed by Grewal, Iyer, Kretschmer, Liang [43] and Anshu and Arunachalam [6]. Previous protocols ran in time $\mathrm{exp}(Θ(n))$ or required $τ>\cos^2(π/8)$. States with stabilizer dimension $n - t$: We give a protocol that runs in time $n^3\cdot(2^t/τ)^{O(\log(1/ε))}$, extending recent work on learning quantum states prepared by circuits with few non-Clifford gates, which only applied in the realizable setting where $τ= 1$ [33, 40, 49, 66]. Discrete product states: If $C = K^{\otimes n}$ for some $μ$-separated discrete set $K$ of single-qubit states, we give a protocol that runs in time $(n/μ)^{O((1 + \log (1/τ))/μ)}/ε^2$. This strictly generalizes a prior guarantee which applied to stabilizer product states [42]. For stabilizer product states, we give a further improved protocol that runs in time $(n^2/ε^2)\cdot (1/τ)^{O(\log(1/τ))}$. As a corollary, we give the first protocol for estimating stabilizer fidelity, a standard measure of magic for quantum states, to error $ε$ in $n^3 \mathrm{quasipoly}(1/ε)$ time.

arXiv:2408.06967•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•5 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

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits

Jonathan Allcock, João Fernando Doriguello, Gábor Ivanyos +1 more

Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unfortunately, however, it is known that Bell sampling fails when used on qu\emph{d}its of dimension $d>2$. In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for $d=p$ prime we devise a quantum algorithm to identify an unknown stabiliser state in $(\mathbb{C}^p)^{\otimes n}$ that uses $O(n)$ copies of the input state and runs in time $O(n^4)$. As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension $d$ using $O(\log{n}/\log{d})$ auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.

arXiv:2405.06357•May 10, 2024•0 citations

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

Agnostic Tomography of Stabilizer Product States

Sabee Grewal, Vishnu Iyer, William Kretschmer +1 more

We define a quantum learning task called agnostic tomography , where given copies of an arbitrary state ρ and a class of quantum states C , the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε ). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ .We give an efficient agnostic tomography algorithm for the class C of n -qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time n O ( log ⁡ ( 2 / τ ) ) / ε 2 , which is p o l y ( n / ε ) for any constant τ .

arXiv:2404.03813•Quantum•Mar 13, 2026•1 citation

Learning unknown stabilizer codes using product measurements

Heather Leitch, Sri. S. Tirukkovalluri, Yingkai Ouyang

Efficiently characterizing quantum error correcting codes is a key challenge on the path to fault-tolerant quantum computation. Stabilizer codes, a central class of such codes, are defined by a set of stabilizer generators. Here, we present an algorithm that uses random single-qubit measurements to learn the stabilizer generators of any stabilizer code from $N$ copies of stabilizer states in its codespace, requiring no prior knowledge of the code's structure. This also enables verification that a device implements its intended code. We derive a lower bound on $N$ needed to recover the stabilizer generators with high probability, together with a bound on the algorithm's overall probability of success. When applied to quantum low-density parity-check (qLDPC) codes, a leading candidate for practical fault-tolerant architectures, our approach requires a number of states that scales polylogarithmically with $n$, the number of qubits.

quant-pharXiv:2609.04997•Sep 7, 2026•0 citations
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.
We study the task of agnostic tomography: given copies of an unknown nnn-qubit state ρρρ which has fidelity τττ with some state in a given class CCC, find a state which has fidelity ≥τ−ε\ge τ- ε≥τ−ε with ρρρ. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: Stabilizer states: We give a protocol that runs in time poly(n,1/ε)⋅(1/τ)O(log⁡(1/τ))\mathrm{poly}(n,1/ε)\cdot (1/τ)^{O(\log(1/τ))}poly(n,1/ε)⋅(1/τ)O(log(1/τ)), answering an open question posed by Grewal, Iyer, Kretschmer, Liang [43] and Anshu and Arunachalam [6]. Previous protocols ran in time exp(Θ(n))\mathrm{exp}(Θ(n))exp(Θ(n)) or required τ>cos⁡2(π/8)τ>\cos^2(π/8)τ>cos2(π/8). States with stabilizer dimension n−tn - tn−t: We give a protocol that runs in time n3⋅(2t/τ)O(log⁡(1/ε))n^3\cdot(2^t/τ)^{O(\log(1/ε))}n3⋅(2t/τ)O(log(1/ε)), extending recent work on learning quantum states prepared by circuits with few non-Clifford gates, which only applied in the realizable setting where τ=1τ= 1τ=1 [33, 40, 49, 66]. Discrete product states: If C=K⊗nC = K^{\otimes n}C=K⊗n for some μμμ-separated discrete set KKK of single-qubit states, we give a protocol that runs in time (n/μ)O((1+log⁡(1/τ))/μ)/ε2(n/μ)^{O((1 + \log (1/τ))/μ)}/ε^2(n/μ)O((1+log(1/τ))/μ)/ε2. This strictly generalizes a prior guarantee which applied to stabilizer product states [42]. For stabilizer product states, we give a further improved protocol that runs in time (n2/ε2)⋅(1/τ)O(log⁡(1/τ))(n^2/ε^2)\cdot (1/τ)^{O(\log(1/τ))}(n2/ε2)⋅(1/τ)O(log(1/τ)). As a corollary, we give the first protocol for estimating stabilizer fidelity, a standard measure of magic for quantum states, to error εεε in n3quasipoly(1/ε)n^3 \mathrm{quasipoly}(1/ε)n3quasipoly(1/ε) time.
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.
Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unfortunately, however, it is known that Bell sampling fails when used on qu\emph{d}its of dimension d>2d>2d>2. In this paper, we explore and quantify the limitations of Bell sampling on qudits, and propose new quantum algorithms to circumvent the use of Bell sampling in solving two important problems: learning stabiliser states and providing pseudorandomness lower bounds on qudits. More specifically, as our first result, we characterise the output distribution corresponding to Bell sampling on copies of a stabiliser state and show that the output can be uniformly random, and hence reveal no information. As our second result, for d=pd=pd=p prime we devise a quantum algorithm to identify an unknown stabiliser state in (Cp)⊗n(\mathbb{C}^p)^{\otimes n}(Cp)⊗n that uses O(n)O(n)O(n) copies of the input state and runs in time O(n4)O(n^4)O(n4). As our third result, we provide a quantum algorithm that efficiently distinguishes a Haar-random state from a state with non-negligible stabiliser fidelity. As a corollary, any Clifford circuit on qudits of dimension ddd using O(log⁡n/log⁡d)O(\log{n}/\log{d})O(logn/logd) auxiliary non-Clifford single-qudit gates cannot prepare computationally pseudorandom quantum states.
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.
We define a quantum learning task called agnostic tomography , where given copies of an arbitrary state ρ and a class of quantum states C , the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε ). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ .We give an efficient agnostic tomography algorithm for the class C of n -qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time n O ( log ⁡ ( 2 / τ ) ) / ε 2 , which is p o l y ( n / ε ) for any constant τ .
Efficiently characterizing quantum error correcting codes is a key challenge on the path to fault-tolerant quantum computation. Stabilizer codes, a central class of such codes, are defined by a set of stabilizer generators. Here, we present an algorithm that uses random single-qubit measurements to learn the stabilizer generators of any stabilizer code from NNN copies of stabilizer states in its codespace, requiring no prior knowledge of the code's structure. This also enables verification that a device implements its intended code. We derive a lower bound on NNN needed to recover the stabilizer generators with high probability, together with a bound on the algorithm's overall probability of success. When applied to quantum low-density parity-check (qLDPC) codes, a leading candidate for practical fault-tolerant architectures, our approach requires a number of states that scales polylogarithmically with nnn, the number of qubits.