pith. sign in

arxiv: 2607.02444 · v1 · pith:7YJ3UH5Lnew · submitted 2026-07-02 · 🪐 quant-ph · cs.CC· cs.DS· cs.IT· cs.LG· math.IT

Optimal Stabilizer Testing and Learning with Limited Quantum Memory

Srinivasan Arunachalam , Louis Schatzki This is my paper

Pith reviewed 2026-07-03 11:38 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.DScs.ITcs.LGmath.IT
keywords stabilizer statesquantum memorysample complexitystate testingstate learninghidden shift problempurity testing
0
0 comments X

The pith

With only k qubits of coherent memory, testing n-qubit stabilizer states requires Θ(n-k) samples.

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

The paper determines the sample complexities of testing and learning stabilizer states when an algorithm may retain only k qubits of coherent quantum memory between measurements on successive copies. Testing requires Θ(n-k) copies, with the upper bound obtained by reduction to the hidden shift problem and the lower bound obtained via a combinatorial argument on average-case likelihood ratios. Learning requires Θ(n²/k) copies in the non-adaptive setting. These bounds show that the separation between constant-copy testing and linear-copy learning disappears under memory limits, and that even near-full memory (k = 0.99n) precludes constant-copy testing.

Core claim

In the k-qubit memory model the sample complexity of testing stabilizer states is Θ(n-k) and the sample complexity of learning them non-adaptively is Θ(n²/k). The testing upper bound follows from a connection to the hidden shift problem; the lower bound follows from a novel combinatorial approach to average-case likelihood ratio bounds that uses the stochastic orthogonal group. Consequently even with k = 0.99n memory a constant-copy tester does not exist, and when k = cn for constant c < 1 both tasks require Θ(n) copies.

What carries the argument

The k-qubit coherent memory model, in which the algorithm receives copies sequentially but may retain only k qubits coherently between measurements.

If this is right

  • Even with 99 percent of full memory, stabilizer testing cannot be performed with a constant number of copies.
  • When memory is a constant fraction cn of the system size, testing and learning have identical Θ(n) sample complexity.
  • Purity testing requires exponentially many copies even when memory may remain fully coherent throughout the protocol.

Where Pith is reading between the lines

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

  • The same memory-dependent separation may appear in testing other structured quantum states if analogous combinatorial lower-bound techniques apply.
  • The non-adaptive learning bound leaves open whether adaptive algorithms could achieve lower sample complexity with the same memory limit.
  • The framework suggests memory size rather than adaptivity alone is the dominant resource separating testing from learning for stabilizer states.

Load-bearing premise

The combinatorial argument that produces average-case likelihood ratio bounds via the stochastic orthogonal group holds and yields the stated lower bound on testing.

What would settle it

An explicit protocol that tests n-qubit stabilizer states with o(n-k) copies while using only k qubits of coherent memory between measurements would falsify the lower bound.

Figures

Figures reproduced from arXiv: 2607.02444 by Louis Schatzki, Srinivasan Arunachalam.

Figure 1
Figure 1. Figure 1: Protocol using k-qubits of memory and single-copy measurements. In each round a new copy of an input state ρ is loaded. There is also a coherent memory register of k-qubits. The operations in each round act on the memory and the input at that step. The channels applied may depend classically upon the prior observations. 1.1 Main results Our main result is to settle both of these questions. Even with 0.99n … view at source ↗
Figure 2
Figure 2. Figure 2: Sample complexity of learning and testing stabilizer states with limited quantum memory. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Partially contracting a swap operation. By contracting the first register of SWAP [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Partial Bell sampling using a quantum memory. Part of the input state [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
read the original abstract

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 $\Theta(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 $\Theta(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 $\Theta(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 $\Theta(n)$ copies.

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 / 2 minor

Summary. The manuscript claims to determine the sample complexities for testing and learning n-qubit stabilizer states when the algorithm has access to only k qubits of coherent quantum memory. Specifically, testing requires Θ(n - k) copies, with the upper bound derived from a connection to the hidden shift problem and the lower bound from a new combinatorial approach to bounding likelihood ratios using the stochastic orthogonal group. Learning requires Θ(n² / k) copies in the non-adaptive setting. The results highlight that coherent quantum memory is the key resource separating testing from learning complexities, as even with k = 0.99n, constant-copy testing is impossible, and for k = cn with c < 1, testing matches learning in requiring Θ(n) copies. An exponential lower bound for purity testing with coherent memory is also provided.

Significance. If the bounds hold, this work significantly advances understanding of quantum resources in property testing and learning by showing how memory constraints eliminate the constant-sample testing advantage for stabilizers established by Gross, Nezami and Walter. The hidden-shift connection for the upper bound and the new combinatorial technique for the lower bound are notable. The results have implications for quantum algorithm design under realistic memory limits and provide tight optimal bounds.

major comments (2)
  1. [Lower bound for stabilizer testing (combinatorial argument via stochastic orthogonal group)] The Θ(n-k) lower bound for testing (central to the claim that coherent memory enables the testing-learning separation and that k=0.99n yields no constant-copy tester) is established via the novel average-case likelihood-ratio bound from combinatorics on the stochastic orthogonal group. This argument is load-bearing; the manuscript should expand the key measure estimates on distinguishable elements (as described in the abstract) to allow independent verification, since no machine-checked proof or prior reference is indicated.
  2. [Learning lower bound (non-adaptive framework)] The non-adaptive learning lower bound of Ω(n²/k) should be checked for consistency with the testing result: if the testing lower bound technique applies directly, it must be shown why it does not yield a stronger learning lower bound that would alter the claimed separation for k=cn.
minor comments (2)
  1. [Abstract] The abstract introduces the stochastic orthogonal group without a brief inline definition or pointer to the relevant section; adding this would improve accessibility for readers unfamiliar with the combinatorial tool.
  2. [Introduction] Notation for memory parameter k and dimension n should be consistently introduced with a short reminder in the introduction before the main theorems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments, which help clarify the presentation of our results on stabilizer testing and learning under memory constraints. We address the major comments below.

read point-by-point responses

  1. Referee: [Lower bound for stabilizer testing (combinatorial argument via stochastic orthogonal group)] The Θ(n-k) lower bound for testing (central to the claim that coherent memory enables the testing-learning separation and that k=0.99n yields no constant-copy tester) is established via the novel average-case likelihood-ratio bound from combinatorics on the stochastic orthogonal group. This argument is load-bearing; the manuscript should expand the key measure estimates on distinguishable elements (as described in the abstract) to allow independent verification, since no machine-checked proof or prior reference is indicated.

    Authors: We agree that the combinatorial argument via the stochastic orthogonal group is central to the Θ(n-k) testing lower bound. In the revised manuscript, we will expand the relevant section to include additional intermediate steps and details on the measure estimates for distinguishable elements, facilitating independent verification of the average-case likelihood ratio bounds. revision: yes

  2. Referee: [Learning lower bound (non-adaptive framework)] The non-adaptive learning lower bound of Ω(n²/k) should be checked for consistency with the testing result: if the testing lower bound technique applies directly, it must be shown why it does not yield a stronger learning lower bound that would alter the claimed separation for k=cn.

    Authors: The testing lower bound technique is tailored to the decision problem of distinguishing whether an unknown state is a stabilizer or Ω(1)-far from every stabilizer; it does not directly apply to the search problem of learning (i.e., outputting a description of the unknown stabilizer). Our Ω(n²/k) non-adaptive learning lower bound is obtained via a separate information-theoretic argument that counts the number of possible n-qubit stabilizers and accounts for the k-qubit memory bottleneck. For k = cn with c < 1 the two bounds coincide at Θ(n), preserving the claimed absence of a testing-learning separation under linear memory constraints. We will add a short clarifying paragraph making this distinction explicit. revision: partial

Circularity Check

0 steps flagged

No circularity; testing and learning bounds derived from independent combinatorial arguments and hidden-shift reduction

full rationale

The paper's central claims rest on an upper bound obtained by reducing stabilizer testing to the hidden-shift problem and a lower bound obtained via a new average-case likelihood-ratio analysis on the stochastic orthogonal group. Neither step is shown to reduce to a prior result by the paper's own equations, self-definition, or self-citation chain; the combinatorial argument is explicitly presented as novel and is not justified by any cited prior work of the authors. The learning bound is likewise obtained by direct non-adaptive analysis. No fitted parameter is relabeled as a prediction, and no uniqueness theorem is imported from the authors' earlier papers. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on abstract only; no explicit free parameters, axioms, or invented entities identified in the provided text.

pith-pipeline@v0.9.1-grok · 5833 in / 1133 out tokens · 33579 ms · 2026-07-03T11:38:25.427755+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

61 extracted references · 61 canonical work pages · 7 internal anchors

  1. [1]

    Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt, and Theodore J. Yoder. Optimal Algorithms for Learning Quantum Phase States . In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023) , volume 266 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 3:1--3:24, 2023

    work page 2023

  2. [2]

    Quantum algorithmic measurement

    Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. Quantum algorithmic measurement. Nature communications , 13(1):887, 2022

    work page 2022

  3. [3]

    Polynomial-time tolerant testing stabilizer states

    Srinivasan Arunachalam and Arkopal Dutt. Polynomial-time tolerant testing stabilizer states. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1234–1241. Association for Computing Machinery, 2025

    work page 2025

  4. [4]

    Identifying stabilizer states, 2009

    Scott Aaronson and Daniel Gottesman. Identifying stabilizer states, 2009. https://pirsa.org/08080052

    work page arXiv 2009

  5. [5]

    On the role of entanglement and statistics in learning

    Srinivasan Arunachalam, Vojtech Havlicek, and Louis Schatzki. On the role of entanglement and statistics in learning. Advances in Neural Information Processing Systems , 36:55064--55076, 2023

    work page 2023

  6. [6]

    Generalized inner product estimation with limited quantum communication

    Srinivasan Arunachalam and Louis Schatzki. Generalized inner product estimation with limited quantum communication. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) , pages 11--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2025

    work page 2025

  7. [7]

    Entanglement is necessary for optimal quantum property testing

    Sebastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 692--703. IEEE, 2020

    work page 2020

  8. [8]

    Product testing with single-copy measurements

    Jacob Beckey, Luke Coffman, Ariel Shlosberg, Louis Schatzki, and Felix Leditzky. Product testing with single-copy measurements. arXiv preprint arXiv:2510.07820 , 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  9. [9]

    A complete theory of the Clifford commutant

    Lennart Bittel, Jens Eisert, Lorenzo Leone, Antonio A Mele, and Salvatore FE Oliviero. A complete theory of the clifford commutant. arXiv preprint arXiv:2504.12263 , 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  10. [10]

    The state hidden subgroup problem and an efficient algorithm for locating unentanglement

    Adam Bouland, Tudor Giurgic a -Tiron, and John Wright. The state hidden subgroup problem and an efficient algorithm for locating unentanglement. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 463--470, 2025

    work page 2025

  11. [11]

    Optimal trace-distance bounds for free-fermionic states: T esting and improved tomography

    Lennart Bittel, Antonio Anna Mele, Jens Eisert, and Lorenzo Leone. Optimal trace-distance bounds for free-fermionic states: T esting and improved tomography. PRX Quantum , 6(3):030341, 2025

    work page 2025

  12. [12]

    Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation

    Zongbo Bao, Philippe van Dordrecht, and Jonas Helsen. Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation. arXiv:2410.21811 , 2024

    work page arXiv 2024

  13. [13]

    Learning quantum processes and hamiltonians via the pauli transfer matrix

    Matthias C Caro. Learning quantum processes and hamiltonians via the pauli transfer matrix. ACM Transactions on Quantum Computing , 5(2):1--53, 2024

    work page 2024

  14. [14]

    Exponential separations between learning with and without quantum memory

    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 574--585. IEEE, 2022

    work page 2021

  15. [15]

    Theoretical framework for quantum networks

    Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Theoretical framework for quantum networks. Physical Review A—Atomic, Molecular, and Optical Physics , 80(2):022339, 2009

    work page 2009

  16. [16]

    Efficient pauli channel estimation with logarithmic quantum memory

    Sitan Chen and Weiyuan Gong. Efficient pauli channel estimation with logarithmic quantum memory. PRX Quantum , 6(2):020323, 2025

    work page 2025

  17. [17]

    Optimal tradeoffs for estimating P auli observables

    Sitan Chen, Weiyuan Gong, and Qi Ye. Optimal tradeoffs for estimating P auli observables. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1086--1105, 2024

    work page 2024

  18. [18]

    Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation

    Sitan Chen, Weiyuan Gong, Qi Ye, and Zhihan Zhang. Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC'25, page 429–438. Association for Computing Machinery, 2025

    work page 2025

  19. [19]

    Tight bounds for quantum state certification with incoherent measurements

    Sitan Chen, Jerry Li, Brice Huang, and Allen Liu. Tight bounds for quantum state certification with incoherent measurements. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 1205--1213. IEEE, 2022

    work page 2022

  20. [20]

    An optimal tradeoff between entanglement and copy complexity for state tomography

    Sitan Chen, Jerry Li, and Allen Liu. An optimal tradeoff between entanglement and copy complexity for state tomography. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1331--1342, 2024

    work page 2024

  21. [21]

    Efficient learning of t -doped stabilizer states with single-copy measurements

    Nai-Hui Chia, Ching-Yi Lai, and Han-Hsuan Lin. Efficient learning of t -doped stabilizer states with single-copy measurements. Quantum , 8:1250, 2024

    work page 2024

  22. [22]

    Tight bounds on pauli channel learning without entanglement

    Senrui Chen, Changhun Oh, Sisi Zhou, Hsin-Yuan Huang, and Liang Jiang. Tight bounds on pauli channel learning without entanglement. Physical Review Letters , 132(18):180805, 2024

    work page 2024

  23. [23]

    Quantum algorithms for algebraic problems

    Andrew M Childs and Wim Van Dam. Quantum algorithms for algebraic problems. Reviews of Modern Physics , 82(1):1--52, 2010

    work page 2010

  24. [24]

    Quantum advantages for pauli channel estimation

    Senrui Chen, Sisi Zhou, Alireza Seif, and Liang Jiang. Quantum advantages for pauli channel estimation. Physical Review A , 105(3):032435, 2022

    work page 2022

  25. [25]

    On quantum algorithms for noncommutative hidden subgroups

    Mark Ettinger and Peter H yer. On quantum algorithms for noncommutative hidden subgroups. Advances in Applied Mathematics , 25(3):239--251, 2000

    work page 2000

  26. [26]

    On the sample complexity of purity and inner product estimation

    Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation. arXiv preprint arXiv:2410.12712 , 2024

    work page arXiv 2024

  27. [27]

    Low- S tabilizer- C omplexity Q uantum S tates Are Not P seudorandom

    Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Low- S tabilizer- C omplexity Q uantum S tates Are Not P seudorandom . In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , Leibniz International Proceedings in Informatics (LIPIcs), pages 64:1--64:20. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2023

    work page 2023

  28. [28]

    Improved S tabilizer E stimation via B ell D ifference S ampling

    Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Improved S tabilizer E stimation via B ell D ifference S ampling. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 1352–1363. Association for Computing Machinery, 2024

    work page 2024

  29. [29]

    Efficient learning of quantum states prepared with few non-clifford gates

    Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Efficient learning of quantum states prepared with few non-clifford gates. Quantum , 9:1907, 2025

    work page 1907

  30. [30]

    Agnostic tomography of stabilizer product states

    Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Agnostic tomography of stabilizer product states. Quantum , 10:2027, 2026

    work page 2027

  31. [31]

    Quantum state isomorphism problems for groups

    Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban, and Arsalan Motamedi. Quantum state isomorphism problems for groups. arXiv preprint arXiv:2605.12615 , 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  32. [32]

    Schur-- W eyl duality for the C lifford group with applications: P roperty testing, a robust H udson theorem, and de F inetti representations

    David Gross, Sepehr Nezami, and Michael Walter. Schur-- W eyl duality for the C lifford group with applications: P roperty testing, a robust H udson theorem, and de F inetti representations. Communications in Mathematical Physics , 385(3):1325--1393, 2021

    work page 2021

  33. [33]

    Toward a general theory of quantum games

    Gus Gutoski and John Watrous. Toward a general theory of quantum games. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 565--574, 2007

    work page 2007

  34. [34]

    The Church of the Symmetric Subspace

    Aram W Harrow. The church of the symmetric subspace. arXiv preprint arXiv:1308.6595 , 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  35. [35]

    Approximate orthogonality of permutation operators, with application to quantum information

    Aram W Harrow. Approximate orthogonality of permutation operators, with application to quantum information. Letters in Mathematical Physics , 114(1):1, 2023

    work page 2023

  36. [36]

    Quantum advantage in learning from experiments

    Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, et al. Quantum advantage in learning from experiments. Science , 376(6598):1182--1186, 2022

    work page 2022

  37. [37]

    Clifford testing: Algorithms and lower bounds

    Marcel Hinsche, Zongbo Bao, Philippe van Dordrecht, Jens Eisert, Jop Bri \"e t, and Jonas Helsen. Clifford testing: Algorithms and lower bounds. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages 869--873, 2026

    work page 2026

  38. [38]

    Abelian state hidden subgroup problem: Learning stabilizer groups and beyond

    Marcel Hinsche, Jens Eisert, and Jose Carrasco. Abelian state hidden subgroup problem: Learning stabilizer groups and beyond. PRX Quantum , 7(2):020337, 2026

    work page 2026

  39. [39]

    Bell sampling from quantum circuits

    Dominik Hangleiter and Michael J Gullans. Bell sampling from quantum circuits. Physical Review Letters , 133(2):020601, 2024

    work page 2024

  40. [40]

    Single-copy stabilizer testing

    Marcel Hinsche and Jonas Helsen. Single-copy stabilizer testing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 439--450, 2025

    work page 2025

  41. [41]

    Efficient quantum algorithms for stabilizer entropies

    Tobias Haug, Soovin Lee, and Myung-Shik Kim. Efficient quantum algorithms for stabilizer entropies. Physical Review Letters , 132(24):240602, 2024

    work page 2024

  42. [42]

    Qubit stabilizer states are complex projective 3-designs

    Richard Kueng and David Gross. Qubit stabilizer states are complex projective 3-designs. arXiv preprint arXiv:1510.02767 , 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  43. [43]

    Triply efficient shadow tomography

    Robbie King, David Gosset, Robin Kothari, and Ryan Babbush. Triply efficient shadow tomography. PRX Quantum , 6:010336, Feb 2025

    work page 2025

  44. [44]

    A subexponential-time quantum algorithm for the dihedral hidden subgroup problem

    Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing , 35(1):170--188, 2005

    work page 2005

  45. [45]

    Quantum channels with memory

    Dennis Kretschmann and Reinhard F Werner. Quantum channels with memory. Physical Review A—Atomic, Molecular, and Optical Physics , 72(6):062323, 2005

    work page 2005

  46. [46]

    The role of randomness in quantum state certification with unentangled measurements

    Yuhan Liu and Jayadev Acharya. The role of randomness in quantum state certification with unentangled measurements. In The Thirty Seventh Annual Conference on Learning Theory , pages 3523--3555. PMLR, 2024

    work page 2024

  47. [47]

    Lower bounds for learning quantum states with single-copy measurements

    Angus Lowe and Ashwin Nayak. Lower bounds for learning quantum states with single-copy measurements. ACM Transactions on Computation Theory , 17(1):1--42, 2025

    work page 2025

  48. [48]

    Stabilizer r \'e nyi entropy

    Lorenzo Leone, Salvatore FE Oliviero, and Alioscia Hamma. Stabilizer r \'e nyi entropy. Physical Review Letters , 128(5):050402, 2022

    work page 2022

  49. [49]

    Learning t-doped stabilizer states

    Lorenzo Leone, Salvatore FE Oliviero, and Alioscia Hamma. Learning t-doped stabilizer states. Quantum , 8:1361, 2024

    work page 2024

  50. [50]

    Learning efficient decoders for quasichaotic quantum scramblers

    Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd, and Alioscia Hamma. Learning efficient decoders for quasichaotic quantum scramblers. Physical Review A , 109(2):022429, 2024

    work page 2024

  51. [51]

    The Hidden Subgroup Problem - Review and Open Problems

    Chris Lomont. The hidden subgroup problem-review and open problems. arXiv preprint quant-ph/0411037 , 2004

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  52. [52]

    Memory-sample lower bounds for learning with classical-quantum hybrid memory

    Qipeng Liu, Ran Raz, and Wei Zhan. Memory-sample lower bounds for learning with classical-quantum hybrid memory. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1097--1110, 2023

    work page 2023

  53. [53]

    Quantum learning in bosonic and fermionic systems

    Antonio Anna Mele. Quantum learning in bosonic and fermionic systems. 2026

    work page 2026

  54. [54]

    Efficient learning of quantum states prepared with few fermionic non-gaussian gates

    Antonio Anna Mele and Yaroslav Herasymenko. Efficient learning of quantum states prepared with few fermionic non-gaussian gates. PRX Quantum , 6(1):010319, 2025

    work page 2025

  55. [55]

    Learning stabilizer states by Bell sampling

    Ashley Montanaro. Learning stabilizer states by B ell sampling. arXiv:1707.04012 , 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  56. [56]

    Improved bounds for testing low stabilizer complexity states

    Saeed Mehraban and Mehrdad Tahmasbi. Improved bounds for testing low stabilizer complexity states. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages 1222--1233, 2025

    work page 2025

  57. [57]

    Sample-optimal quantum process tomography with non-adaptive incoherent measurements

    Aadil Oufkir. Sample-optimal quantum process tomography with non-adaptive incoherent measurements. In 2023 IEEE International Symposium on Information Theory (ISIT) , pages 1919--1924. IEEE, 2023

    work page 2023

  58. [58]

    Quantum computation and lattice problems

    Oded Regev. Quantum computation and lattice problems. SIAM Journal on Computing , 33(3):738--760, 2004

    work page 2004

  59. [59]

    Quantum algorithms for highly non-linear boolean functions

    Martin R \"o tteler. Quantum algorithms for highly non-linear boolean functions. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms , pages 448--457. SIAM, 2010

    work page 2010

  60. [60]

    On the power of quantum computation

    Daniel R Simon. On the power of quantum computation. SIAM journal on computing , 26(5):1474--1483, 1997

    work page 1997

  61. [61]

    Quantum algorithms for some hidden shift problems

    Wim Van Dam, Sean Hallgren, and Lawrence Ip. Quantum algorithms for some hidden shift problems. SIAM Journal on Computing , 36(3):763--778, 2006

    work page 2006