pith. machine review for the scientific record. sign in

arxiv: 2604.24099 · v1 · submitted 2026-04-27 · 🪐 quant-ph

Recognition: unknown

Single-copy stabilizer learning: average case and worst case

Gyungmin Cho , Dohun Kim
Authors on Pith no claims yet

Pith reviewed 2026-05-08 04:21 UTC · model grok-4.3

classification 🪐 quant-ph
keywords stabilizer learningsingle-copy measurementsClifford circuitsaverage-case analysisworst-case lower boundsPauli symmetriesquantum state learning
0
0 comments X

The pith

Logarithmic-depth local Clifford circuits suffice to learn almost all stabilizer groups with t=O(log n) from single copies.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that in typical cases, shallow circuits of logarithmic depth can identify the stabilizer group of an n-qubit state with only O(log n) errors using single-copy measurements, replacing the deeper linear-depth circuits needed before. This matters for practical quantum state learning because it lowers the resource demands for extracting Pauli symmetries when the underlying group is drawn from a natural distribution. In contrast, the work proves that no adaptive single-copy scheme can succeed in the worst case without a number of samples that grows exponentially with the error parameter t. The two results together indicate that single-copy learning is feasible on average for moderate t but becomes information-theoretically hard without multiple copies when t is large.

Core claim

In the average case over random stabilizer groups of codimension t, logarithmic-depth local Clifford circuits allow efficient learning of almost all such groups for t = O(log n); any adaptive single-copy measurement protocol requires a sample complexity exponential in t in the worst case.

What carries the argument

Logarithmic-depth local Clifford circuits that generate single-copy measurements to extract the stabilizer group on average, paired with an information-theoretic argument establishing exponential sample lower bounds for arbitrary adaptive single-copy POVMs.

If this is right

  • Stabilizer learning becomes practical for typical states with up to logarithmic errors using circuits whose depth grows only with log n.
  • Single-copy measurements suffice for efficient average-case identification of Pauli symmetries when t remains moderate.
  • For large t the sample complexity gap between single-copy and two-copy schemes implies a quantum advantage in the learning setting.
  • Resource estimates for symmetry extraction in quantum devices can be reduced by focusing on typical rather than adversarial cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The average-case protocol may generalize to other structured quantum learning tasks where the target objects follow a natural ensemble.
  • Near-term hardware with limited circuit depth could still perform useful stabilizer learning by exploiting the prevalence of typical groups.
  • The exponential worst-case lower bound suggests exploring hybrid single- and two-copy strategies for intermediate t values.
  • The separation between average and worst case may appear in related problems such as learning other quantum symmetries or error-correcting codes.

Load-bearing premise

The average-case efficiency holds only under a uniform or natural distribution over stabilizer groups of codimension t, while the worst-case bound requires the input to be exactly a stabilizer state plus t errors.

What would settle it

A numerical or analytic counter-example showing that some fraction of random stabilizer states with t = log n errors cannot be identified with high probability using any log-depth local Clifford single-copy protocol, or an explicit adaptive single-copy scheme that learns arbitrary stabilizer states with poly(t) samples.

Figures

Figures reproduced from arXiv: 2604.24099 by Dohun Kim, Gyungmin Cho.

Figure 1
Figure 1. Figure 1: FIG. 1. Comparison of measurement protocols. (a) Bell view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Numerical simulations. (a) Learning Weyl( view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Quotient reduction. Left: for a fixed isotropic subspace view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Recovery under noisy computational difference samples. We fix view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Numerical simulations for learning stabilizer groups with different Clifford ensembles. We compare the number view at source ↗
read the original abstract

We study single-copy stabilizer learning, the problem of identifying a stabilizer group of dimension $n-t$ from an $n$-qubit quantum state $\rho$. We obtain two complementary results. First, in the average case, logarithmic-depth local Clifford circuits suffice to efficiently learn almost all stabilizer groups with $t=O(\log n)$, instead of the linear-depth measurements required in previous approaches. We support this result with numerical simulations for systems of up to 100 qubits. Second, we show that, in the worst case, any adaptive single-copy measurement scheme requires a number of samples that scales exponentially in $t$. Together with existing results on two-copy learning, our findings suggest that, for large $t$, identifying Pauli symmetries of a quantum system exhibits a quantum advantage in the learning setting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript studies single-copy stabilizer learning: identifying an (n-t)-dimensional stabilizer group from an n-qubit state. It claims that, in the average case, logarithmic-depth local Clifford circuits suffice to efficiently learn almost all such groups when t=O(log n), supported by numerical simulations up to 100 qubits; and that, in the worst case, any adaptive single-copy measurement scheme requires a number of samples exponential in t. Together with prior two-copy results, this is said to indicate a quantum advantage for large t in learning Pauli symmetries.

Significance. The worst-case exponential lower bound is a clear and load-bearing contribution that rigorously separates single-copy from multi-copy learning in the adversarial setting. The numerical evidence up to n=100 for typical instances with t=log n is a positive empirical finding that could guide practical protocols if the average-case claim is formalized. If the average-case result holds under a well-defined measure, the work would usefully highlight an average/worst-case separation in quantum symmetry learning.

major comments (2)
  1. [Abstract] Abstract and main results section: The claim that 'logarithmic-depth local Clifford circuits suffice to efficiently learn almost all stabilizer groups with t=O(log n)' is presented as a result but is supported only by numerical simulations. No formal theorem, explicit distribution over (n-t)-dimensional stabilizer groups, or asymptotic argument showing that the success probability approaches 1 is provided. This is load-bearing for the central average-case contribution and requires either a proof or a precise statement that the claim is conjectural.
  2. [Numerical Simulations] Numerical evidence section (supporting the average-case claim): The simulations reach n=100 but the manuscript does not specify the exact sampling procedure used to generate 'random' stabilizer groups of codimension t, nor does it report failure probabilities, confidence intervals, or scaling of the hard-instance fraction with n. Without these, it is impossible to assess whether the observed success rate implies that the measure of hard groups vanishes asymptotically.
minor comments (1)
  1. [Throughout] Clarify the precise definition of 'local Clifford circuits' (e.g., whether locality is on the interaction graph or on the support of each gate) and ensure consistent use of the codimension parameter t throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the constructive comments. We address the two major points below and describe the revisions we will make to clarify the status of the average-case claim and to strengthen the presentation of the numerical evidence.

read point-by-point responses

  1. Referee: [Abstract] Abstract and main results section: The claim that 'logarithmic-depth local Clifford circuits suffice to efficiently learn almost all stabilizer groups with t=O(log n)' is presented as a result but is supported only by numerical simulations. No formal theorem, explicit distribution over (n-t)-dimensional stabilizer groups, or asymptotic argument showing that the success probability approaches 1 is provided. This is load-bearing for the central average-case contribution and requires either a proof or a precise statement that the claim is conjectural.

    Authors: We agree that the average-case statement is an empirical observation rather than a theorem. In the revised manuscript we will rephrase the abstract and the corresponding paragraph in the main results section to present the claim explicitly as a conjecture: that logarithmic-depth local Clifford circuits suffice to learn almost all (n-t)-dimensional stabilizer groups for t = O(log n). We will also add a precise definition of the distribution over stabilizer groups used in the simulations and a brief discussion of the observed scaling of the success probability with n. revision: yes

  2. Referee: [Numerical Simulations] Numerical evidence section (supporting the average-case claim): The simulations reach n=100 but the manuscript does not specify the exact sampling procedure used to generate 'random' stabilizer groups of codimension t, nor does it report failure probabilities, confidence intervals, or scaling of the hard-instance fraction with n. Without these, it is impossible to assess whether the observed success rate implies that the measure of hard groups vanishes asymptotically.

    Authors: We will expand the numerical simulations section to include: (i) the exact procedure used to sample random (n-t)-dimensional stabilizer groups (via the standard uniform distribution on the Grassmannian of isotropic subspaces of the Pauli space), (ii) the number of independent trials performed for each (n,t) pair, (iii) the observed failure rates together with binomial confidence intervals, and (iv) a plot or table showing the fraction of hard instances as a function of n for fixed t/log n. These additions will make the empirical support for the conjecture fully reproducible and allow readers to assess the asymptotic trend. revision: yes

Circularity Check

0 steps flagged

No significant circularity; average-case result rests on simulations and worst-case bound on standard information-theoretic arguments

full rationale

The paper presents an average-case claim supported by numerical simulations for n up to 100 and a worst-case exponential lower bound derived from adaptive single-copy POVM analysis. Neither result reduces to its inputs by construction, fitted parameters renamed as predictions, or load-bearing self-citations. The claims rely on external assumptions about uniform distributions over stabilizer groups and exact knowledge of stabilizer states plus errors, without self-definitional loops or ansatz smuggling. This is the expected non-finding for a paper whose central results are simulation-backed and information-theoretic rather than closed algebraic derivations.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on standard quantum information axioms about stabilizer states, Clifford circuits, and single-copy measurements; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Stabilizer states and groups are defined via the standard Pauli operator formalism on n qubits.
    Invoked throughout the problem definition and bounds.
  • domain assumption Single-copy measurements correspond to adaptive POVMs on individual copies of the state.
    Central to both the upper and lower bounds stated.

pith-pipeline@v0.9.0 · 5423 in / 1327 out tokens · 31761 ms · 2026-05-08T04:21:30.200943+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references · 8 canonical work pages

  1. [1]

    bS⊇Weyl(ρ), 2.E x∼ bS tr(ρWx)2 ≥1−ϵ. 3 Algorithm 1:Approximating Weyl(ρ) using single-copy shallow-depth measurements Input:O(n 32t/ϵ) copies ofρandϵ∈(0,0.25) Promise:dim Weyl(ρ) =n−t Output:A subspace bS⊇Weyl(ρ) of dimension at leastn−tsuch thatE x∼ bStr(ρWx)2 ≥1−ϵ with high probability 1Takem=O(n2 t) 2fori= 1tomdo 3SampleC i ∼ C k and defineρ i =C iρC †...

    2023

  2. [2]

    Gottesman,Stabilizer codes and quantum error cor- rection(California Institute of Technology, 1997)

    D. Gottesman,Stabilizer codes and quantum error cor- rection(California Institute of Technology, 1997)

    1997

  3. [3]

    A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics303, 2 (2003)

    2003

  4. [4]

    Kueng, D

    R. Kueng and D. Gross, Qubit stabilizer states are complex projective 3-designs, arXiv preprint arXiv:1510.02767 (2015)

    work page arXiv 2015

  5. [5]

    Haferkamp, F

    J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eis- ert, D. Gross, and I. Roth, Efficient unitary designs with a system-size independent number of non-clifford gates: J. haferkamp, f. montealegre-mora, m. heinrich, j. eis- ert, d. gross, i. roth, Communications in Mathematical Physics397, 995 (2023)

    2023

  6. [6]

    B. Zeng, X. Chen, D.-L. Zhou, and X.-G. Wen, Quantum information meets quantum matter–from quantum en- tanglement to topological phase in many-body systems, 6 arXiv preprint arXiv:1508.02595 (2015)

    work page arXiv 2015

  7. [7]

    C. G. Brell, S. T. Flammia, S. D. Bartlett, and A. C. Do- herty, Toric codes and quantum doubles from two-body hamiltonians, New Journal of Physics13, 053039 (2011)

    2011

  8. [8]

    Kitaev, Anyons in an exactly solved model and be- yond, Annals of Physics321, 2 (2006)

    A. Kitaev, Anyons in an exactly solved model and be- yond, Annals of Physics321, 2 (2006)

    2006

  9. [9]

    S. J. Evered, M. Kalinowski, A. A. Geim, T. Manovitz, D. Bluvstein, S. H. Li, N. Maskara, H. Zhou, S. Ebadi, M. Xu,et al., Probing the kitaev honeycomb model on a neutral-atom quantum computer, Nature645, 341 (2025)

    2025

  10. [10]

    M. Will, T. Cochran, E. Rosenberg, B. Jobst, N. M. Eassa, P. Roushan, M. Knap, A. Gammon-Smith, and F. Pollmann, Probing non-equilibrium topological order on a quantum processor, Nature645, 348 (2025)

    2025

  11. [11]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Information- theoretic bounds on quantum advantage in machine learning, Physical Review Letters126, 190505 (2021)

    2021

  12. [12]

    Grewal, V

    S. Grewal, V. Iyer, W. Kretschmer, and D. Liang, Effi- cient learning of quantum states prepared with few non- clifford gates, Quantum9, 1907 (2025)

    1907

  13. [13]

    Hangleiter and M

    D. Hangleiter and M. J. Gullans, Bell sampling from quantum circuits, Physical Review Letters133, 020601 (2024)

    2024

  14. [14]

    Leone, S

    L. Leone, S. F. Oliviero, and A. Hamma, Learning t- doped stabilizer states, Quantum8, 1361 (2024)

    2024

  15. [15]

    Gross, S

    D. Gross, S. Nezami, and M. Walter, Schur–weyl duality for the clifford group with applications: Property test- ing, a robust hudson theorem, and de finetti represen- tations, Communications in Mathematical Physics385, 1325 (2021)

    2021

  16. [16]

    S. Chen, W. Gong, Q. Ye, and Z. Zhang, Stabilizer boot- strapping: A recipe for efficient agnostic tomography and magic estimation, inProceedings of the 57th Annual ACM Symposium on Theory of Computing(2025) pp. 429–438

    2025

  17. [17]

    Maslov and M

    D. Maslov and M. Roetteler, Shorter stabilizer circuits via bruhat decomposition and quantum circuit transfor- mations, IEEE Transactions on Information Theory64, 4729 (2018)

    2018

  18. [18]

    Chia, C.-Y

    N.-H. Chia, C.-Y. Lai, and H.-H. Lin, Efficient learning of t-doped stabilizer states with single-copy measurements, Quantum8, 1250 (2024)

    2024

  19. [19]

    Cho and D

    G. Cho and D. Kim, Entanglement-enhanced randomized measurement in noisy quantum devices, arXiv preprint arXiv:2504.15698 (2025)

    work page arXiv 2025

  20. [20]

    Cho and D

    G. Cho and D. Kim, Sample-optimal single-copy quan- tum state tomography via shallow depth measurements, arXiv preprint arXiv:2509.12703 (2025)

    work page arXiv 2025

  21. [21]

    F. G. Brand˜ ao, R. Kueng, and D. S. Fran¸ ca, Fast and robust quantum state tomography from few basis mea- surements, arXiv preprint arXiv:2009.08216 (2020)

    work page arXiv 2009

  22. [22]

    Bertoni, J

    C. Bertoni, J. Haferkamp, M. Hinsche, M. Ioannou, J. Eisert, and H. Pashayan, Shallow shadows: Expecta- tion estimation using low-depth random clifford circuits, Physical Review Letters133, 020602 (2024)

    2024

  23. [23]

    Bouland, T

    A. Bouland, T. Giurgic˘ a-Tiron, and J. Wright, The state hidden subgroup problem and an efficient algorithm for locating unentanglement, inProceedings of the 57th An- nual ACM Symposium on Theory of Computing(2025) pp. 463–470

    2025

  24. [24]

    arXiv preprint arXiv:2505.15770 , year=

    M. Hinsche, J. Eisert, and J. Carrasco, The abelian state hidden subgroup problem: Learning stabilizer groups and beyond, arXiv preprint arXiv:2505.15770 (2025)

    work page arXiv 2025

  25. [25]

    Arunachalam, S

    S. Arunachalam, S. Bravyi, A. Dutt, and T. J. Yoder, Optimal algorithms for learning quantum phase states, arXiv preprint arXiv:2208.07851 (2022)

    work page arXiv 2022

  26. [26]

    S. Chen, J. Cotler, H.-Y. Huang, and J. Li, Exponen- tial separations between learning with and without quan- tum memory, in2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2022) pp. 574–585

    2022

  27. [27]

    S. Chen, W. Gong, and Q. Ye, Optimal tradeoffs for estimating pauli observables, in2024 IEEE 65th An- nual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2024) pp. 1086–1105

    2024

  28. [28]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth, Science389, 92 (2025)

    2025

  29. [29]

    Learning stabilizer states by Bell sampling

    A. Montanaro, Learning stabilizer states by bell sam- pling, arXiv preprint arXiv:1707.04012 (2017)

    work page Pith review arXiv 2017

  30. [30]

    Hinsche and J

    M. Hinsche and J. Helsen, Single-copy stabilizer testing, inProceedings of the 57th Annual ACM Symposium on Theory of Computing(2025) pp. 439–450

    2025

  31. [31]

    H.-Y. Hu, A. Gu, S. Majumder, H. Ren, Y. Zhang, D. S. Wang, Y.-Z. You, Z. Minev, S. F. Yelin, and A. Seif, Demonstration of robust and efficient quantum property learning with shallow shadows, Nature Communications 16, 2943 (2025)

    2025

  32. [32]

    Huang, R

    H.-Y. Huang, R. Kueng, G. Torlai, V. V. Albert, and J. Preskill, Provably efficient machine learning for quan- tum many-body problems, Science377, eabk3333 (2022)

    2022

  33. [33]

    Lowe and A

    A. Lowe and A. Nayak, Lower bounds for learning quan- tum states with single-copy measurements, ACM Trans- actions on Computation Theory17, 1 (2025)

    2025

  34. [34]

    Goldreich and L

    O. Goldreich and L. A. Levin, A hard-core predicate for all one-way functions, inProceedings of the 21st An- nual ACM Symposium on Theory of Computing (STOC) (1989) pp. 25–32

    1989

  35. [35]

    Bombin and M

    H. Bombin and M. A. Martin-Delgado, Topological quan- tum distillation, Physical Review Letters97, 180501 (2006). Appendix A: Related work a. Multi-copy and single-copy stabilizer learning.Previous work on stabilizer learning has explored both multi- copy [11–13, 28] and single-copy measurement settings [11, 17]. Multi-copy methods are often more efficien...

    2006

  36. [36]

    We analyze Algorithm 1, which learns Weyl(ρ) using only single-copy shallow-depth measurements

    bS⊇Weyl(ρ), 2.E x∼ bS tr(ρWx)2 ≥1−ϵ. We analyze Algorithm 1, which learns Weyl(ρ) using only single-copy shallow-depth measurements. The proof has two parts: first, we show that random Clifford circuits fromC k reveal enough information to recover Weyl(ρ); second, we bound the number of computational difference samples needed to recover the hidden Pauli s...

  37. [37]

    (E88) gives γ(n, m, κ) = 1 + 3(2κ −1) 2m −1 2n −1 + (2κ −1)(2 κ −2) (2m −1)(2 m−1 −1) (2n −1)(2 n−1 −1) (E92) ≤1 + 3·2 κ+m−n + 4κ+m−n.(E93) This proves the claim

    Therefore, Pr S (Ud ⊆S) = n−d m−d 2 n m 2 .(E89) 19 In particular, Pr S (U1 ⊆S) = 2m −1 2n −1 ,(E90) Pr S (U2 ⊆S) = (2m −1)(2 m−1 −1) (2n −1)(2 n−1 −1) .(E91) Substituting these into Eq. (E88) gives γ(n, m, κ) = 1 + 3(2κ −1) 2m −1 2n −1 + (2κ −1)(2 κ −2) (2m −1)(2 m−1 −1) (2n −1)(2 n−1 −1) (E92) ≤1 + 3·2 κ+m−n + 4κ+m−n.(E93) This proves the claim

  38. [38]

    , Cm ∼ Ck, the resulting measurement bases are sufficient to recover the full stabilizer group

    Part I: Recovery of the Weyl support In the first part, we show that, whent=O(logn), with high probability over independently sampledC 1, . . . , Cm ∼ Ck, the resulting measurement bases are sufficient to recover the full stabilizer group. Concretely, we show that mX i=1 Weyl(ρ)∩C † i (Z) = Weyl(ρ) (E94) holds with high probability. This conclusion does n...

  39. [39]

    , Cm ∼ C k, one obtains measurement bases that are sufficient to recover Weyl(ρ)

    Part II: Reconstruction from computational difference samples In Part I, we showed that, after samplingm=O(n2 t) Clifford circuitsC 1, . . . , Cm ∼ C k, one obtains measurement bases that are sufficient to recover Weyl(ρ). This, however, does not by itself identify the generators of Weyl(ρ). It remains to show that, in each such basis, sufficiently many c...

  40. [40]

    , xm aremi.i.d

    Suppose x1, . . . , xm aremi.i.d. samples drawn fromD. Fix0< δ <1. Ifm≥ 2 log(1/δ)+2d ϵ , then with probability at least1−δ, D(span(x1, . . . , xm))≥1−ϵ.(E157) Applying this fact to the computational difference sampling distributionr ρ yields the following. 25 Corollary 6.Letx 1, . . . , xm bemi.i.d. computational difference samples drawn fromr ρ, and let...

  41. [41]

    bS⊇Weyl(ρ), 2.E x∼ bS tr(ρWx)2 ≥1−ϵ,

  42. [42]

    In particular, bSis a valid output of Algorithm 1

    bSis isotropic. In particular, bSis a valid output of Algorithm 1. Proof.By Corollary 4, with high probability over the choice ofC 1, . . . , Cm, we have mX i=1 Weyl(ρ)∩C † i (Z) = Weyl(ρ) (E200) for all but a 2 −Ω(n) fraction of Weyl(ρ)∈ I n−t(V). Fix such aρ, and for eachi∈[m] define Hi := Weyl(ρi)∩ Z ⊥ ∩ X.(E201) By Corollary 2, every computational dif...

  43. [43]

    1 |bS| X x∈ bS tr(ρWx)2 ≥1−ϵ, (H2)

  44. [44]

    bSis isotropic. (H3) We will show that the existence of such an algorithm would imply an efficient single-copy protocol for a previously studied hypothesis-testing problem that is known to require Ω(2 t) samples. This yields the desired lower bound. Consider the following two families of states: ρA = 0n−t 0n−t ⊗ I 2t ,with probability 1 2 ,(H4) ρB = 0n−t ...

  45. [45]

    1 |bS| X x∈ bS tr(ρWx)2 ≥1−ϵ, for everyn-qubit stateρwithdim Weyl(ρ) =n−t, must use at leastΩ(2 t)copies in the worst case. Previous single-copy learning algorithms [11, 17] were established mainly for pure-state inputs, so, taken in iso- lation, a lower bound based on mixed-state hypotheses could be viewed as an artifact of the particular mixed-state con...