Pith. sign in

REVIEW 2 major objections 4 minor 3 cited by

Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes a general sufficient condition—approximate state 2-design—for quantum hypothesis-testing problems to be low-degree hard, and uses it to derive new information-computation gaps.

desk verdict A valuable quantum low-degree framework whose headline Gibbs-state degree claim outstrips what the main theorem's proof actually supports; the framework and most applications survive, but the Ω(n)-degree corollary needs reining in. read the letter →

arxiv 2505.22743 v2 pith:CG52LJRV submitted 2025-05-28 quant-ph cs.CCcs.DScs.LG

Sitan Chen , Weiyuan Gong , Jonas Haferkamp , Yihui Quek This is my paper
classification quant-phcs.CCcs.DScs.LG MSC 81P6868Q17 PACS 03.67.Lx
keywords quantumlearninglow-degreemethodinformation-computationgapstatedesignshypothesistestingmeasurementsplantedbicliqueerrormitigation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper extends the classical low-degree method to quantum learning, certifying hardness by showing that no low-degree polynomial in the measurement readouts can distinguish a candidate ensemble from the maximally mixed state. Its central claim is that approximate state 2-designs—ensembles whose two-copy statistics match Haar-random states—are enough for this certificate, making the testing problem degree-k hard for non-adaptive single-copy measurements with O(n) ancillas. The authors use this connection to obtain the first information-computation gaps for learning Gibbs states of random sparse non-local Hamiltonians, hardness for random shallow quantum circuit states under restricted adaptivity, and low-degree hardness for quantum error mitigation with single-qubit measurements. They also introduce a quantum planted-biclique problem with a sharp local-measurement threshold, and prove average-case low-degree hardness for Learning Stabilizers with Noise and for agnostically learning product states. Because the low-degree method is heuristic evidence, these are computational-gap predictions conditional on the low-degree conjecture.

What carries the argument

The load-bearing object is the low-degree likelihood ratio of the classical readout distribution induced by the chosen measurements, and the sufficient condition is that the alternative ensemble is an approximate state 2-design; a second-moment match with the Haar measure makes all small Fourier coefficients of the likelihood ratio negligible after averaging over the measurement. Technically, the proofs combine a copy-wise degree notion with Naimark dilation and unitary decompositions that let O(n)-ancilla PVMs be reduced to product forms, and represent adaptive protocols as block-structured learning trees so that moment bounds can be propagated by induction over blocks.

What would settle it

To falsify the central claim, one could construct an ensemble E that is a $2^{-\tilde{\Omega}(k\log n)}$-approximate state 2-design and give a poly(n)-time algorithm using poly(n) single-copy measurements with O(n) ancillas that distinguishes E from the maximally mixed state with constant advantage; this would be a quantum counterexample to the low-degree conjecture as applied in Theorem 6.7. A concrete starting point is to test the random sparse signed Pauli Hamiltonian ensemble: if a polynomial-time Gibbs-state learner exists, the claimed $\Omega(n)$-degree hardness for Corollary 8.15 would fail.

Watch

Extended reading notes

Core claim

Stated on the paper's own terms, the discovery is a general transfer: if the alternative ensemble E is a $2^{-\tilde{\Omega}(k \log n)}$-approximate state 2-design, then distinguishing $\rho = I/2^n$ from $\rho \sim E$ using $m = \mathrm{poly}(n)$ copies is degree-k hard for any non-adaptive single-copy measurement strategy whose PVMs are implemented with at most $O(n)$ ancillas (Theorem 6.7). The same design condition, at higher design order or with block structure, yields hardness for projective measurements in adaptively chosen bases under two round-based models (Theorem 1.2). From these conditions the paper derives the first information-computation gaps for Gibbs states of random sparse non-local Hamiltonians, polylog-depth random circuit states, and quantum error mitigation at inverse-polynomial noise rate, plus fine-grained thresholds for the new quantum planted-biclique problem and average-case hardness for Learning Stabilizers with Noise and agnostic tomography of product states.

Load-bearing premise

The load-bearing premise is the low-degree conjecture: whenever the degree-k low-degree likelihood advantage is o(1), no $(nm)^{O(k)}$-time distinguisher can achieve weak detection, and this conjecture is not proved and is known to fail for some algebraic problems (Section 3.6).

Editorial extensions

If this is right

  • If Theorem 6.7 is correct, approximate state 2-designs are a generic hardness certificate: any single-copy measurement strategy with poly(n) copies and O(n) ancillas cannot be turned into a low-degree distinguisher.
  • Gibbs states of random sparse non-local Hamiltonians at inverse temperature $\beta = 1$ become degree-$\Omega(n)$ hard to distinguish from maximally mixed under non-adaptive single-copy PVMs, giving the first evidence that this learning task is computationally hard.
  • Random polylog-depth geometrically local circuit states are degree-polylog(n) hard to distinguish from maximally mixed, extending prior distributional hardness to all single-copy measurement strategies with limited adaptivity.
  • Quantum error mitigation is low-degree hard against single-qubit measurement strategies even with only constantly many layers of $O(1/n^{1-\delta'})$ depolarizing noise, a regime that is not statistically hard.
  • Quantum planted biclique exhibits a threshold: local measurements are degree-$n^{o(1)}$ hard below $\lambda \approx n^{1/2}d^{1/4}$, while local computational-basis counting succeeds above it, defining a new average-case quantum learning problem with tunable signal-to-noise ratio.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the same 2-design certificate may apply to candidate pseudorandom ensembles: matching second moments plus a modest approximate-design guarantee would give low-degree hardness for many learning tasks at once, offering a route to hardness evidence without cryptographic assumptions.
  • Editorial inference: the quantum planted-biclique landscape suggests that the measurement class itself changes computational complexity; a non-local single-copy algorithm below $\lambda = \omega(n^{2/3})$ would sharpen this into a clean separation between local and entangled single-copy measurements.
  • Editorial inference: the paper's no-go results imply that fully adaptive low-degree models can hide arbitrary computation in the choice of bases, so any future adaptivity framework must bound the complexity of choosing measurements rather than only the degree of post-processing.
  • Editorial inference: because degree-2 moments suffice for hardness under single-copy measurements, the paper suggests a quantum degree-magnification phenomenon in which two-copy statistical indistinguishability upgrades to computational indistinguishability of polynomially many copies.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. This paper develops a quantum generalization of the classical low-degree method for hypothesis testing of quantum states. The central structural result (Theorem 6.7) shows that if the alternative ensemble is an approximate state 2-design, then distinguishing it from the maximally mixed state is degree-k hard for non-adaptive single-copy PVM strategies with O(n) ancillas. The paper then introduces a copy-wise degree model and two round-based adaptive measurement models, and applies the framework to quantum error mitigation, random shallow circuits, Gibbs states of sparse non-local Hamiltonians, a new quantum planted biclique problem, Learning Stabilizers with Noise, and agnostic tomography of product states. All computational-hardness interpretations are explicitly conditional on the low-degree conjecture, and the paper candidly discusses known counterexamples to that conjecture.

Significance. The conceptual core of the paper is valuable: it shows that a second-moment condition (approximate 2-design) can be upgraded to low-degree hardness against essentially arbitrary single-copy measurements, and it introduces adaptive measurement models that are new to the low-degree literature. The applications are broad and the paper is unusually transparent about its limitations, including the low-degree conjecture, the restriction to PVMs with at most roughly n/11 ancillas, and the no-go results for stronger adaptivity in Section 7.5. However, the advertised degree-O(n) Gibbs hardness is not supported by the proof as written; the framework as proved gives degree-n^{o(1)} hardness (e.g., polylog) for the ancilla-assisted single-copy setting. This materially tempers the headline contribution, although the main structural connection between designs and low-degree hardness remains sound in its corrected range.

major comments (2)
  1. [§6.2, Eq. (7) and Theorem 6.7] The parameter regime stated in Theorem 6.7 is inconsistent with the proof. In the line after Eq. (7), the choice n' ≤ (n - Ω~(k log n))/11 is called Θ(n), but this is valid only when k log n = o(n). For k = Θ(n), any n' = Θ(n) makes the exponent |T| + 11n' - n equal to Θ(n), so the right-hand side of Eq. (7) is not 2^{-Ω~(k log n)}; the subsequent sum over (mn)^k Fourier coefficients then gives an advantage of the form exp(Θ(n log n)), not o(1). Consequently Theorem 6.7, as stated for arbitrary k with ε ≤ 2^{-Ω~(k log n)}, is not proved for k = Θ(n). This overclaim propagates to Corollary 8.9, Theorem 8.14, Corollary 8.15, and the informal Corollary 1.4 (degree-Ω(n) hardness). The framework as proved does support degree-k hardness for k = n^{o(1)} (in particular polylog), so the results should be restated in that range unless a genuinely new argument is supplied.
  2. [§6.2, Theorem 6.7, after Eq. (7)] The proof concludes a local-indistinguishability bound that holds with probability at least 1 - m(2·2^{|T|+11n'-n}+3ε)^{1/2} over the random state ψ, but the hypothesis of Theorem 6.6 requires the expectation over ψ of the trace distance. Because trace distance is always at most 1, the failure event contributes at most m(2·2^{|T|+11n'-n}+3ε)^{1/2} to the expectation; this term should be added to the right-hand side before the final conclusion. In the stated parameter range this extra term is harmless and the theorem can be repaired, but as written the final step from the high-probability statement to the expectation is missing.
minor comments (4)
  1. [Introduction, Theorem 1.6 and §9.1, Theorem 9.1] The informal threshold in Theorem 1.6, λ ≤ \tilde{o}(n^{1/2}d^{1/4}), omits the number of copies m that appears in the formal Theorem 9.1 as λ ≤ o(n d^{1/4} m^{-1/2}). Please state explicitly that the informal version corresponds to m = n (or otherwise specify the m-dependence).
  2. [§9, problem definition] The phrase 'maximally maxed state' in the introduction to quantum planted biclique should read 'maximally mixed state'.
  3. [§9.3, Proposition 9.5 proof] In the first paragraph of the proof, the text says the measurement outcome is distributed as Ber(1/2+Θ(1/√d)) if the qudit is a copy of ρ and also as Ber(1/2+Θ(1/√d)) if it is a copy of I/d; the second branch should presumably be Ber(1/2).
  4. [§7.2, after Condition 7.6] The phrase 'At a first glance' should be 'At first glance'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central framework derives low-degree hardness from approximate state 2-designs; the k=Theta(n) overclaim is a proof-range issue, not a circular step.

full rationale

The paper's central derivation chain is self-contained rather than circular. Theorem 6.7 proves degree-k low-degree hardness for non-adaptive single-copy PVMs with O(n) ancillas under the assumption that the ensemble is a 2^{-\tilde{\Omega}(k log n)}-approximate state 2-design; the hardness conclusion is a mathematical consequence of the design condition plus local indistinguishability, not an input assumed into the conclusion. Applications to random circuits, Gibbs states, error mitigation, and quantum planted biclique use external facts (design constructions, random matrix bounds, Haar moment calculations) and contain no fitted parameters that are later renamed as predictions. The low-degree conjecture (Conjecture 1) is explicitly stated as an informal conjecture, and Section 3.6 acknowledges known counterexamples (k-XORSAT and Buhai et al.); this makes the interpretation of low-degree hardness as computational hardness conditional, but that is a caveat about the framework's semantics, not a circular derivation. Self-citations are not load-bearing: the equivalence with statistical queries in Section 7.4 imports the classical result of [23], and the shallow-circuit design bounds rely on external results such as [108]. The specific skeptic concern about Theorem 6.7 is real but is not circularity: the proof's statement 'choose n' <= (n - \tilde{\Omega}(k log n))/11 = Theta(n)' is only valid when k log n = o(n), so Corollary 8.15's claimed k <= O(n) (and hence degree-Omega(n) for Gibbs states) is not supported by the proved framework. That is an internal consistency / theorem-range issue in the manuscript, not a reduction of the claimed prediction to its own inputs. The paper does not define hardness in terms of the ensembles it predicts to be hard, and it does not fit parameters to data and call the fit a prediction. Therefore no circular step can be exhibited under the standard patterns, and the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No new particles, forces, dimensions, or conserved quantities are introduced. The new objects are models and problems, such as the copy-wise low-degree model, round-based adaptivity, and quantum planted biclique. These are not physical entities, so the invented entities ledger is empty. There are no free parameters fitted to data; lambda, d, m0, m1, and k are natural problem parameters, not fitted constants.

assumptions (6)
  • domain assumption Low-degree conjecture (Conjecture 1, Section 2.2): bounded low-degree likelihood ratio implies no efficient distinguisher for natural problems.
    This unproved conjecture converts all low-degree hardness statements in the paper into information-computation gap claims. Section 3.6 documents counterexamples (k-XORSAT via Gaussian elimination; Buhai et al. quasipolynomial algorithm), so it is load-bearing and not established.
  • domain assumption Approximate state/unitary k-design constructions for shallow random circuits (Lemma 8.7 from [64, 108]).
    Used in Corollaries 8.8, 8.10, and 8.11 to assert that polylog-depth circuits form the designs needed by the framework; the accuracy-depth tradeoffs are imported rather than proved.
  • domain assumption Classical low-degree hardness of planted dense subgraph/biclique and tensor PCA.
    Used to interpret the quantum planted biclique threshold (Section 9.1) and the tensor PCA encoding (Section 10.2). These are standard low-degree predictions from [23, 86], not proved here.
  • domain assumption Eigenvalue concentration and third moment matching of random sparse Pauli Hamiltonians to GUE (Fact 8.13 and Eq. (18) from [29]).
    Used in Theorem 8.14 and Corollary 8.15 to ensure Gibbs states are mixtures of eigenstates with bounded eigenvalues and design-like eigenvector statistics.
  • standard math Fact 2.1 Haar moment formula and unitary decomposition into product terms (Section 6.2).
    Background Haar integration and the quantum Shannon or Cosine-Sine decomposition used in Theorem 6.7 are quoted from [66, 109] without proof.
  • standard math Naimark dilation and the assumption that arbitrary POVMs can be represented as PVMs on enlarged systems with ancillas.
    Section 2.1 uses this to justify the ancilla-assisted PVM model; it is standard but load-bearing for the measurement class considered.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood." pith.science (2026). https://pith.science/paper/CG52LJRV

@misc{pith2026250522743,
  author       = {Pith},
  title        = {Pith review of: Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CG52LJRV}},
  note         = {Machine review of arXiv:2505.22743}
}
read the original abstract

In a variety of physically relevant settings for learning from quantum data, designing protocols that can computationally efficiently extract information remains largely an art, and there are important cases where we believe this to be impossible, that is, where there is an information-computation gap. While there is a large array of tools in the classical literature for giving evidence for average-case hardness of statistical inference problems, the corresponding tools in the quantum literature are far more limited. One such framework in the classical literature, the low-degree method, makes predictions about hardness of inference problems based on the failure of estimators given by low-degree polynomials. In this work, we extend this framework to the quantum setting. We establish a general connection between state designs and low-degree hardness. We use this to obtain the first information-computation gaps for learning Gibbs states of random, sparse, non-local Hamiltonians. We also use it to prove hardness for learning random shallow quantum circuit states in a challenging model where states can be measured in adaptively chosen bases. To our knowledge, the ability to model adaptivity within the low-degree framework was open even in classical settings. In addition, we also obtain a low-degree hardness result for quantum error mitigation against strategies with single-qubit measurements. We define a new quantum generalization of the planted biclique problem and identify the threshold at which this problem becomes computationally hard for protocols that perform local measurements. Interestingly, the complexity landscape for this problem shifts when going from local measurements to more entangled single-copy measurements. We show average-case hardness for the "standard" variant of Learning Stabilizers with Noise and for agnostically learning product states.

Figures

Figures reproduced from arXiv: 2505.22743 by the authors.

Figure 1
Figure 1. Non-adaptive single-copy PVM on one copy of [PITH_FULL_IMAGE:figures/full_fig_p026_1.png] view at source ↗
Figure 2
Figure 2. (a) The non-adaptive copy-wise low-degree model where each term of the final function depends on [PITH_FULL_IMAGE:figures/full_fig_p032_2.png] view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications

    cs.LG 2025-09 conditional novelty 8.0 of 10

    A new potential-based algorithm achieves instance-optimal O(sqrt(T·S(X||I/d))) regret for matrix LEA with the same complexity as MMWU, using a one-sided Jensen trace inequality.

  2. Efficient learning of bosonic Gaussian unitaries

    quant-ph 2025-10 conditional novelty 7.0 of 10

    We present the first provably efficient algorithm, in both query and time complexity, for learning arbitrary multi-mode bosonic Gaussian unitaries under the energy-constrained diamond distance.

  3. Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

    math.ST 2025-06 accept novelty 2.0 of 10

    A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.

Reference graph

Works this paper leans on

122 extracted references · 26 canonical work pages · cited by 3 Pith papers

  1. [1]

    Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou,Quantum pseudoentanglement, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2024, 2211.00747

    arXiv 2024

  2. [2]

    Scott Aaronson and Daniel Gottesman,Identifying stabilizer states, Perimeter Institute Recorded Seminar Archive (2008)

    2008

  3. [3]

    Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, and Nathan Srebro,On the power of differentiable learning versus pac and sq learning, Advances in Neural Information Processing Systems34 (2021)

    2021

  4. [4]

    Quantum Algorithmic Measurement

    Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi,Quantum algorithmic measurement, Nature communications13 (2022), no. 887, 2101.04634

    work page Pith review arXiv 2022

  5. [5]

    118, Cambridge University Press, 2010

    Greg W Anderson, Alice Guionnet, and Ofer Zeitouni,An introduction to random matrices, no. 118, Cambridge University Press, 2010

    2010

  6. [6]

    685–691, IEEE, 2020, 2004.07266

    Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar,Sample- efficient learning of quantum many-body systems, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 685–691, IEEE, 2020, 2004.07266

    arXiv 2020

  7. [7]

    , Efficient learning of commuting Hamiltonians on lattices, Unpublished notes avaible at Anurag Anshu’s website,(link to note) (2021)

    2021

  8. [8]

    Srinivasan Arunachalam, Alex B Grilo, and Henry Yuen,Quantum statistical query learning, arXiv preprint arXiv:2002.08240 (2020)

    arXiv 2020

Show all 122 references
  1. [9]

    Srinivasan Arunachalam, Vojtech Havlicek, and Louis Schatzki,On the role of entanglement and statistics in learning, Advances in Neural Information Processing Systems36 (2023)

    2023

  2. [10]

    Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, jerry Li, Allen Liu, Ryan O’Donnell, and Ewin Tang, Learning the closest product state , arXiv:2411.04283 (2024), 2411.04283

    2024

  3. [11]

    1470–1477, 2024, 2310.02243

    Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang,Learning quantum Hamiltonians at any temperature in polynomial time, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1470–1477, 2024, 2310.02243

    2024 arXiv

  4. [12]

    1, 2108.06312

    AfonsoSBandeira,MarchTBoedihardjo,andRamonvanHandel, Matrixconcentrationinequalities and free probability, Inventiones mathematicae234 (2023), no. 1, 2108.06312

    2023 arXiv

  5. [13]

    549–560, 2024

    Kiril Bangachev and Guy Bresler,On the fourier coefficients of high-dimensional random geometric graphs, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 549–560, 2024

    2024

  6. [14]

    2, 1604.03084

    Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin, A nearly tight sum-of-squares lower bound for the planted clique problem, SIAM Journal on Computing48 (2019), no. 2, 1604.03084

    2019 arXiv

  7. [15]

    1046–1066, PMLR, 2013

    Quentin Berthet and Philippe Rigollet,Complexity theoretic lower bounds for sparse principal component detection, Conference on learning theory, pp. 1046–1066, PMLR, 2013. 72

    2013

  8. [16]

    278–291, 1994

    Avrim Blum, Merrick Furst, Michael Kearns, and Richard J Lipton,Cryptographic primitives based on hard learning problems, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology, pp. 278–291, 1994

    1994

  9. [17]

    John Bostanci, Jonas Haferkamp, Dominik Hangleiter, and Alexander Poremba,Efficient quantum pseudorandomness from hamiltonian phase states, arXiv preprint arXiv:2410.08073 (2024)

    2024 arXiv

  10. [18]

    6, 2201.05142

    Tatiana Brailovskaya and Ramon van Handel, Universality and sharp matrix concentration inequalities, Geometric and Functional Analysis34 (2024), no. 6, 2201.05142

    2024 arXiv

  11. [19]

    619–635, Springer, 2019

    Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, and Daniel Wichs,Worst-case hardness for lpn and cryptographic hashing via code smoothing, Annual international conference on the theory and applications of cryptographic techniques, pp. 619–635, Springer, 2019

    2019

  12. [20]

    Fernando GSL Brandao, Aram W Harrow, and Michał Horodecki,Local random quantum circuits are approximate polynomial-designs, Communications in Mathematical Physics346 (2016), 1208.0692

    2016 arXiv

  13. [21]

    648–847, PMLR, 2020

    Matthew Brennan and Guy Bresler,Reducibility and statistical-computational gaps from secret leakage, Conference on Learning Theory, pp. 648–847, PMLR, 2020

    2020

  14. [22]

    48–166, PMLR, 2018

    Matthew Brennan, Guy Bresler, and Wasim Huleihel,Reducibility and computational lower bounds for problems with planted sparse structure, Conference On Learning Theory, pp. 48–166, PMLR, 2018

    2018

  15. [23]

    Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, and Tselil Schramm,Statistical query algorithms and low degree tests are almost equivalent, Proceedings of Thirty Fourth Conference on Learning Theory (Mikhail Belkin and Samory Kpotufe, eds.), Proceedings of Machine Learn...

    2021 arXiv

  16. [24]

    5850–5889, PMLR, 2023

    Guy Bresler and Tianze Jiang,Detection-recovery and detection-refutation gaps via reductions from planted clique, The Thirty Sixth Annual Conference on Learning Theory, pp. 5850–5889, PMLR, 2023

    2023

  17. [25]

    1398–1411, 2021,2011.10908

    Costin Buadescu and Ryan O’Donnell,Improved quantum data analysis, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1398–1411, 2021,2011.10908

    2021 arXiv

  18. [26]

    692–703, IEEE, 2020, 2004.07869

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

    2020 arXiv

  19. [27]

    Kothari,The quasi-polynomial low-degree conjecture is false, 2025, 2505.17360

    Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, and Pravesh K. Kothari,The quasi-polynomial low-degree conjecture is false, 2025, 2505.17360

    2025 arXiv

  20. [28]

    1193–1203, SIAM, 2014

    Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant,Optimal algorithms for testing closeness of discrete distributions, Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 1193–1203, SIAM, 2014

    2014

  21. [29]

    1,2302.03394

    Chi-Fang Chen, Alexander M Dalzell, Mario Berta, Fernando GSL Brandão, and Joel A Tropp, Sparse random Hamiltonians are quantumly easy,PhysicalReview X 14(2024),no. 1,2302.03394

    2024 arXiv

  22. [30]

    Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan, Incompressibility and spectral gaps of random circuits, arXiv:2406.07478 (2024), 2406.07478. 73

    2024 arXiv

  23. [31]

    18,2309.13461

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

    2024 arXiv

  24. [32]

    574–585, IEEE, 2022, 2111.05881

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

    2021 arXiv

  25. [33]

    1, 2210.07234

    , The complexity of NISQ, Nature Communications14 (2023), no. 1, 2210.07234

    2023 arXiv

  26. [34]

    Sitan Chen, Aravind Gollakota, Adam Klivans, and Raghu Meka,Hardness of noise-free learning for two-hidden-layer neural networks, Advances in Neural Information Processing Systems35 (2022)

    2022

  27. [35]

    Sitan Chen and Weiyuan Gong,Efficient Pauli channel estimation with logarithmic quantum memory, arXiv:2309.14326 (2023), 2309.14326

    2023

  28. [36]

    1086–1105, 2024, 2404.19105

    Sitan Chen, Weiyuan Gong, and Qi Ye,Optimal tradeoffs for estimating pauli observables, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1086–1105, 2024, 2404.19105

    2024 arXiv

  29. [37]

    Sitan Chen,Weiyuan Gong,Qi Ye,and Zhihan Zhang,Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation, arXiv:2408.06967 (2024), 2408.06967

    2024 arXiv

  30. [38]

    Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke,When does adaptivity help for quantum state learning?,2023 IEEE 64thAnnualSymposium on Foundations ofComputerScience (FOCS), IEEE, 2023, 2206.05265

    2023 arXiv

  31. [39]

    1205–1213, IEEE, 2022, 2204.07155

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

    2022 arXiv

  32. [40]

    Sitan Chen, Jerry Li, and Yuanzhi Li,Learning (very) simple generative models is hard, Advances in Neural Information Processing Systems35 (2022)

    2022

  33. [41]

    Sitan Chen, Jerry Li, and Allen Liu,Optimal high-precision shadow estimation, arXiv:2407.13874 (2024), 2407.13874

    2024 arXiv

  34. [42]

    1331–1342, 2024, 2402.16353

    , An optimal tradeoff between entanglement and copy complexity for state tomography, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1331–1342, 2024, 2402.16353

    2024 arXiv

  35. [43]

    4764–4781, PMLR, 2022

    Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein, and Ilias Zadik, Statistical and computational phase transitions in group testing, Conference on Learning Theory, pp. 4764–4781, PMLR, 2022

    2022

  36. [44]

    1, 1101.4366

    Marcus Cramer, Martin B Plenio, Steven T Flammia, Rolando Somma, David Gross, Stephen D Bartlett,OlivierLandon-Cardinal,DavidPoulin,andYi-Kai Liu, Efficientquantum statetomography, Nature communications1 (2010), no. 1, 1101.4366

    2010 arXiv

  37. [45]

    Abhishek Dhawan, Cheng Mao, and Alexander S Wein,Detection of dense subhypergraphs by low-degree polynomials, Random Structures & Algorithms66 (2025), no. 1

    2025

  38. [46]

    4258–4282, PMLR, 2022

    Ilias Diakonikolas and Daniel Kane,Near-optimal statistical query hardness of learning halfspaces with massart noise, Conference on Learning Theory, pp. 4258–4282, PMLR, 2022. 74

    2022

  39. [47]

    1514– 1539, PMLR, 2020

    Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, and Nikos Zarifis,Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks, Conference on Learning Theory, pp. 1514– 1539, PMLR, 2020

    2020

  40. [48]

    73–84, IEEE, 2017, 1611.03473

    Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart,Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 73–84, IEEE, 2017, 1611.03473

    2017 arXiv

  41. [49]

    3, 1907.11635

    Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira,Subexponential-time algorithms for sparse PCA, Foundations of Computational Mathematics 24 (2024), no. 3, 1907.11635

    2024 arXiv

  42. [50]

    Bill Fefferman,Soumik Ghosh,Makrand Sinha,and Henry Yuen,The hardness of learning quantum circuits and its cryptographic applications, (2024)

    2024

  43. [51]

    2, 1201.1214

    Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao,Statistical algorithms and a lower bound for detecting planted cliques, Journal of the ACM (JACM)64 (2017), no. 2, 1201.1214

    2017 arXiv

  44. [52]

    77–86, 2015, 1311.4821

    Vitaly Feldman, Will Perkins, and Santosh Vempala,On the complexity of random satisfiability problems with planted solutions, Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, pp. 77–86, 2015, 1311.4821

    2015 arXiv

  45. [53]

    3587–3596, PMLR, 2020

    Surbhi Goel, Aravind Gollakota, Zhihan Jin, Sushrut Karmalkar, and Adam Klivans, Superpolynomial lower bounds for learning one-layer neural networks using gradient descent, International Conference on Machine Learning, pp. 3587–3596, PMLR, 2020

    2020

  46. [54]

    Surbhi Goel, Aravind Gollakota, and Adam Klivans,Statistical-query lower bounds via functional gradients, Advances in Neural Information Processing Systems33 (2020)

    2020

  47. [55]

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

    2024 arXiv

  48. [56]

    Latorre, Arnau Riera, and Karol Życzkowski,Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices, Phys

    Dardo Goyeneche, Daniel Alsina, José I. Latorre, Arnau Riera, and Karol Życzkowski,Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices, Phys. Rev. A92 (2015)

    2015

  49. [57]

    Dardo Goyeneche and Karol Życzkowski,Genuinely multipartite entangled states and orthogonal arrays, Physical Review A90 (2014), no. 2

    2014

  50. [58]

    Sabee Grewal,Vishnu Iyer,William Kretschmer,andDanielLiang,Agnostictomographyofstabilizer product states, arXiv:2404.03813 (2024), 2404.03813

    2024

  51. [59]

    1352–1363, 2024, 2304.13915

    ,Improved stabilizer estimation via Bell difference sampling, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1352–1363, 2024, 2304.13915

    2024

  52. [60]

    AndiGu,LorenzoLeone,SoumikGhosh,JensEisert,SusanneF.Yelin,andYihuiQuek, Pseudomagic quantum states, Physical Review Letters132 (2024), no. 21

    2024

  53. [61]

    Andi Gu, Yihui Quek, Susanne Yelin, Jens Eisert, and Lorenzo Leone,Simulating quantum chaos without chaos, 2024, 2410.18196. 75

    2024 arXiv

  54. [62]

    913–925, 2016, 1508.01797

    Jeongwan Haah, Aram W Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu,Sample-optimal tomographyofquantum states,Proceedings ofthe Forty-eighthAnnualACM Symposium on Theory of Computing, pp. 913–925, 2016, 1508.01797

    2016 arXiv

  55. [63]

    135–146, IEEE, 2022, 2108.04842

    Jeongwan Haah, Robin Kothari, and Ewin Tang,Optimal learning of quantum Hamiltonians from high-temperature Gibbs states, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 135–146, IEEE, 2022, 2108.04842

    2022

  56. [64]

    Haferkamp,Random quantum circuits are approximate unitary𝑡-designs in depth𝑂(𝑛𝑡5+𝑜(1)), Quantum 6 (2022), 2203.16571

    J. Haferkamp,Random quantum circuits are approximate unitary𝑡-designs in depth𝑂(𝑛𝑡5+𝑜(1)), Quantum 6 (2022), 2203.16571

    2022 arXiv

  57. [65]

    899–928, PMLR, 2015

    Bruce Hajek, Yihong Wu, and Jiaming Xu,Computational lower bounds for community detection on random graphs, Conference on Learning Theory, pp. 899–928, PMLR, 2015

    2015

  58. [66]

    Aram W Harrow,The church of the symmetric subspace, arXiv:1308.6595 (2013)

    2013 arXiv

  59. [67]

    Matthew B Hastings,Classical and quantum algorithms for tensor principal component analysis, Quantum 4 (2020)

    2020

  60. [68]

    Patrick Hayden, Debbie W Leung, and Andreas Winter, Aspects of generic entanglement , Communications in mathematical physics265 (2006), quant-ph/0407049

    2006 arXiv

  61. [69]

    24, 2207.03140

    Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter, J-P Seifert, Jens Eisert, and Ryan Sweke,One t gate makes distribution learning hard, Physical Review Letters130 (2023), no. 24, 2207.03140

    2023 arXiv

  62. [70]

    Marcel Hinsche, Marios Ioannou, Alexander Nietner, Jonas Haferkamp, Yihui Quek, Dominik Hangleiter,Jean-Pierre Seifert,JensEisert,andRyan Sweke, Learnabilityofthe outputdistributions of local quantum circuits, 2021, 2110.05517

    2021 arXiv

  63. [71]

    Justin Holmgren and Alexander S Wein, Counterexamples to the low-degree conjecture , arXiv:2004.08454 (2020), 2004.08454

    2020 arXiv

  64. [72]

    thesis,CornellUniversity, 2018

    SamuelHopkins, Statisticalinferenceandthesumofsquaresmethod ,Ph.D. thesis,CornellUniversity, 2018

    2018

  65. [73]

    720–731, IEEE, 2017

    Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer,The power of sum-of-squares for detecting hidden structures, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 720–731, IEEE, 2017

    2017

  66. [74]

    956–1006, PMLR, 2015

    Samuel B Hopkins, Jonathan Shi, and David Steurer,Tensor principal component analysis via sum-of-square proofs, Conference on Learning Theory, pp. 956–1006, PMLR, 2015

    2015

  67. [75]

    379–390, IEEE, 2017, 1710.00264

    Samuel B Hopkins and David Steurer,Efficient bayesian estimation from few samples: community detection and related problems, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 379–390, IEEE, 2017, 1710.00264

    2017 arXiv

  68. [76]

    Hong-Ye Hu, Muzhou Ma, Weiyuan Gong, Qi Ye, Yu Tong, Steven T Flammia, and Susanne F Yelin, Ansatz-free hamiltonian learning with heisenberg-limited scaling, arXiv preprint arXiv:2502.11900 (2025)

    2025

  69. [77]

    10, 2002.08953

    Hsin-Yuan Huang, Richard Kueng, and John Preskill,Predicting many properties of a quantum system from very few measurements, Nature Physics16 (2020), no. 10, 2002.08953. 76

    2020 arXiv

  70. [78]

    19, 2101.02464

    , Information-theoretic bounds on quantum advantage in machine learning, Physical Review Letters 126 (2021), no. 19, 2101.02464

    2021 arXiv

  71. [79]

    1343–1351, 2024, 2401.10095

    Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R McClean,Learning shallow quantum circuits, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1343–1351, 2024, 2401.10095

    2024 arXiv

  72. [80]

    Gullans, Sarang Gopalakrishnan, David A

    Matteo Ippoliti, Michael J. Gullans, Sarang Gopalakrishnan, David A. Huse, and Vedika Khemani, Entanglement phase transitions in measurement-only dynamics, Phys. Rev. X11 (2021)

    2021

  73. [81]

    Matteo Ippoliti and Vedika Khemani,Learnability transitions in monitored quantum dynamics via eavesdropper’s classical shadows, PRX Quantum5 (2024), no. 2

    2024

  74. [82]

    126–152, Springer, 2018

    Zhengfeng Ji, Yi-Kai Liu, and Fang Song,Pseudorandom quantum states, Advances in Cryptology– CRYPTO 2018: 38thAnnualInternationalCryptologyConference,Santa Barbara,CA,USA,August 19–23, 2018, Proceedings, Part III 38, pp. 126–152, Springer, 2018

    2018

  75. [83]

    Michael Kearns,Efficient noise-tolerant learning from statistical queries,Journal of the ACM (JACM) 45 (1998), no. 6

    1998

  76. [84]

    Hyun-Soo Kim, Isaac H Kim, and Daniel Ranard,Learning state preparation circuits for quantum phases of matter, arXiv:2410.23544 (2024), 2410.23544

    2024 arXiv

  77. [85]

    Robbie King, David Gosset, Robin Kothari, and Ryan Babbush,Triply efficient shadow tomography, arXiv:2404.19211 (2024), 2404.19211

    2024 arXiv

  78. [86]

    1–50, Springer, 2019,1907.11636

    Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira,Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio, ISAAC Congress (International Society for Analysis, its Applications and Computation), pp. 1–50, Springer, 2019,1907.11636

    2019 arXiv

  79. [87]

    Zeph Landau and Yunchao Liu,Learning quantum states prepared by shallow circuits in polynomial time, arXiv:2410.23618 (2024), 2410.23618

    2024 arXiv

  80. [88]

    511–515, IEEE, 2017

    Thibault Lesieur, Léo Miolane, Marc Lelarge, Florent Krzakala, and Lenka Zdeborová,Statistical andcomputationalphase transitions in spikedtensorestimation,2017 ieee internationalsymposium on information theory (isit), pp. 511–515, IEEE, 2017

    2017

  81. [89]

    672–677, 2022

    Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang,Testing thresholds for high- dimensional sparse random geometric graphs, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 672–677, 2022

    2022

  82. [90]

    Fermi Ma and Hsin-Yuan Huang, How to construct random unitaries , arXiv preprint arXiv:2410.10116 (2024)

    2024 arXiv

  83. [91]

    Muzhou Ma, Steven T Flammia, John Preskill, and Yu Tong,Learning𝑘-body hamiltonians via compressed sensing, arXiv preprint arXiv:2410.18928 (2024)

    2024 arXiv

  84. [92]

    Zongming Ma and Yihong Wu,Computational barriers in minimax submatrix detection, (2015)

    2015

  85. [93]

    3798–3822, PMLR, 2024

    Jay Mardia, Kabir Aladin Verchand, and Alexander S Wein,Low-degree phase transitions for detecting a planted clique in sublinear time, The Thirty Seventh Annual Conference on Learning Theory, pp. 3798–3822, PMLR, 2024. 77

    2024

  86. [94]

    Andrea Montanari and Emile Richard,A statistical model for tensor pca, Advances in neural information processing systems27 (2014)

    2014

  87. [95]

    Ashley Montanaro, Learning stabilizer states by Bell sampling , arXiv:1707.04012 (2017), 1707.04012

    2017 arXiv

  88. [96]

    MA Naimark,About second-kind self-adjoint extensions of symmetrical operator, Izv. Akad. Nauk USSR, Ser. Mat4 (1940)

    1940

  89. [97]

    Shyam Narayanan,Improved algorithms for learning quantum Hamiltonians, via flat polynomials, arXiv:2407.04540 (2024), 2407.04540

    2024 arXiv

  90. [98]

    Alexander Nietner, Marios Ioannou, Ryan Sweke, Richard Kueng, Jens Eisert, Marcel Hinsche, and Jonas Haferkamp,On the average-case complexity of learning output distributions of quantum circuits, arXiv:2305.05765 (2023), 2305.05765

    2023

  91. [99]

    529–538, 2015, 1501.05028

    Ryan O’Donnell and John Wright,Quantum spectrum testing, Proceedings of the Forty-seventh Annual ACM Symposium on Theory of computing, pp. 529–538, 2015, 1501.05028

    2015 arXiv

  92. [100]

    899–912, 2016, 1508.01907

    , Efficient quantum tomography, Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pp. 899–912, 2016, 1508.01907

    2016 arXiv

  93. [101]

    Patel, Igor L

    Ketan N. Patel, Igor L. Markov, and John P. Hayes,Optimal synthesis of linear reversible circuits, Quantum Info. Comput.8 (2008), no. 3

    2008

  94. [102]

    Alexander Poremba, Yihui Quek, and Peter Shor,The learning stabilizers with noise problem, arXiv:2410.18953 (2024), 2410.18953

    2024 arXiv

  95. [103]

    Aaron Potechin and Goutham Rajendran,Sub-exponential time sum-of-squares lower bounds for principal components analysis, Advances in Neural Information Processing Systems35 (2022)

    2022

  96. [104]

    10, 2210.11505

    Yihui Quek, Daniel Stilck França, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert, Exponentially tighter bounds on limitations of quantum error mitigation, Nature Physics20 (2024), no. 10, 2210.11505

    2024 arXiv

  97. [105]

    http://www.w3.org/1998/math/mathml

    Zahra Raissi, Adam Teixidó, Christian Gogolin, and Antonio Acín,Constructions of <mml:math xmlns:mml="http://www.w3.org/1998/math/mathml"><mml:mi>k</mml:mi></mml:math> -uniform and absolutely maximally entangled states beyond maximum distance codes, Physical Review Research2 (...

    2020

  98. [106]

    94–1, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023

    Cynthia Rush, Fiona Skerman, Alexander S Wein, and Dana Yang,Is it easier to count communities than find them?, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), pp. 94–1, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023

    2023

  99. [107]

    905–913, SIAM, 2025

    Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, and Ryan Babbush,Quartic quantum speedups for planted inference, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 905–913, SIAM, 2025

    2025

  100. [108]

    Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang,Random unitaries in extremely low depth, arXiv:2407.07754 (2024), 2407.07754

    2024 arXiv

  101. [109]

    272–275, 2005, quant-ph/0406176

    Vivek V Shende, Stephen S Bullock, and Igor L Markov,Synthesis of quantum logic circuits, Proceedings of the 2005 Asia and South Pacific Design Automation Conference, pp. 272–275, 2005, quant-ph/0406176. 78

    2005 arXiv

  102. [110]

    Skinner, J

    B. Skinner, J. Ruhman, and A. Nahum,Measurement-induced phase transitions in the dynamics of entanglement, Phys. Rev. X9 (2019)

    2019

  103. [111]

    Ryota Tomioka and Taiji Suzuki,Spectral norm of random tensors, arXiv:1407.1870 (2014), 1407.1870

    2014 arXiv

  104. [112]

    3, 1305.0612

    JoelATropp, Second-ordermatrixconcentrationinequalities ,AppliedandComputationalHarmonic Analysis 44 (2018), no. 3, 1305.0612

    2018 arXiv

  105. [113]

    1-2, 1501.01571

    Joel A Tropp et al.,An introduction to matrix concentration inequalities, Foundations and Trends® in Machine Learning8 (2015), no. 1-2, 1501.01571

    2015 arXiv

  106. [114]

    Francisca Vasconcelos and Hsin-Yuan Huang,Learning shallow quantum circuits with many-qubit gates, arXiv:2410.16693 (2024), 2410.16693

    2024 arXiv

  107. [115]

    1446–1468, IEEE, 2019

    Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore,The kikuchi hierarchy and tensor pca, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS),pp. 1446–1468, IEEE, 2019

    2019

  108. [116]

    Eugene P Wigner,On the distribution of the roots of certain symmetric matrices, Annals of Mathematics 67 (1958), no. 2

    1958

  109. [117]

    Ales Wodecki and Jakub Marecek, Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexity, arXiv:2402.05552 (2024), 2402.05552

    2024 arXiv

  110. [118]

    473–501,Springer, 2021

    Yu Yu and Jiang Zhang,Smoothing out binary linear codes and worst-case sub-exponential hardness for lpn, Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021,Virtual Event,August 16–20,2021,Proceedings,Part III 41,pp. 473–501,Springer, 2021

    2021

  111. [119]

    4, 2310.19882

    Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C Caro, Learning quantum states and unitaries of bounded gate complexity, PRX Quantum5 (2024), no. 4, 2310.19882

    2024 arXiv

  112. [120]

    6, 1510.02619

    Huangjun Zhu,Multiqubit Clifford groups are unitary 3-designs, Physical Review A96 (2017), no. 6, 1510.02619. 79 A The corner case: Low-degree hardness of learning stabilizer states Here, we also provide a proof of low-degree hardness for learning stabilizer states, which is a...

    2017 arXiv

  113. [121]

    all elements commute), 2.−𝐼 ∉𝐺, where𝐼 is the𝑛-qubit identity operator,

    𝐺 is abelian (i.e. all elements commute), 2.−𝐼 ∉𝐺, where𝐼 is the𝑛-qubit identity operator,

  114. [122]

    A stabilizer stateis any state that is the simultaneous+1 eigenstate of a maximal stabilizer group𝐺, i.e

    |𝐺| = 2𝑟 for some𝑟≤𝑛. A stabilizer stateis any state that is the simultaneous+1 eigenstate of a maximal stabilizer group𝐺, i.e. one with𝑛 generators. The task of learning stabilizer states is the following: Definition A.1(Learning stabilizer states). Input: 𝑚 copies of|𝜓⟩, whe...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.