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

Sample-optimal learning of stabilizer states

Rebecca Chang, Matthias C. Caro, Martin Larocca, Maxwell West

quant-phSubmitted Sep 10, 2026• Announced Sep 11, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

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

Improved Stabilizer Estimation via Bell Difference Sampling

Sabee Grewal, Vishnu Iyer, William Kretschmer +1 more

We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: We prove that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist. Given an n-qubit pure quantum state |ψ⟩ that has fidelity at least τ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least τ − ε. The algorithm uses O(n/(ε2τ4)) samples and exp(O(n/τ4)) / ε2 time. In the regime of τ constant, this algorithm estimates stabilizer fidelity substantially faster than the naive exp(O(n2))-time brute-force algorithm over all stabilizer states. In the special case of τ > cos2(π/8), we show that a modification of the above algorithm runs in polynomial time. We exhibit a tolerant property testing algorithm for stabilizer states. The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory.

arXiv:2304.13915•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•18 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 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

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

Cloning is as Hard as Learning for Stabilizer States

Nikhil Bansal, Matthias C. Caro, Gaurav Mahajan

The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question for an important class of states. Namely, for $n$-qubit stabilizer states, we show that the optimal sample complexity of cloning is $Θ(n)$. Thus, also for this structured class of states, cloning is as hard as learning. To prove these results, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.

quant-pharXiv:2604.15269•Apr 17, 2026•0 citations
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.
We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: We prove that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist. Given an n-qubit pure quantum state |ψ⟩ that has fidelity at least τ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least τ − ε. The algorithm uses O(n/(ε2τ4)) samples and exp(O(n/τ4)) / ε2 time. In the regime of τ constant, this algorithm estimates stabilizer fidelity substantially faster than the naive exp(O(n2))-time brute-force algorithm over all stabilizer states. In the special case of τ > cos2(π/8), we show that a modification of the above algorithm runs in polynomial time. We exhibit a tolerant property testing algorithm for stabilizer states. The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory.
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.
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 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.
The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question for an important class of states. Namely, for nnn-qubit stabilizer states, we show that the optimal sample complexity of cloning is Θ(n)Θ(n)Θ(n). Thus, also for this structured class of states, cloning is as hard as learning. To prove these results, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.