{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T09:15:32Z","timestamp":1768986932781,"version":"3.49.0"},"reference-count":78,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T00:00:00Z","timestamp":1760313600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on n<\/mml:mi><\/mml:math> qubits of depth d<\/mml:mi><\/mml:math>, we show three main results:\u2013 At super logarithmic circuit depth d<\/mml:mi>=<\/mml:mo>&#x03C9;<\/mml:mi>(<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo>)<\/mml:mo><\/mml:math>, any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance.\u2013 There exists a d<\/mml:mi>=<\/mml:mo>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math>, such that any learning algorithm requires &#x03A9;<\/mml:mi>(<\/mml:mo>2<\/mml:mn>n<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:math> queries to achieve a O<\/mml:mi>(<\/mml:mo>2<\/mml:mn>&#x2212;<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math> probability of success over the randomly drawn instance.\u2013 At infinite circuit depth d<\/mml:mi>&#x2192;<\/mml:mo>&#x221E;<\/mml:mi><\/mml:math>, any learning algorithm requires 2<\/mml:mn>2<\/mml:mn>&#x03A9;<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:msup><\/mml:math> many queries to achieve a 2<\/mml:mn>&#x2212;<\/mml:mo>2<\/mml:mn>&#x03A9;<\/mml:mi>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:msup><\/mml:math> probability of success over the randomly drawn instance.As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability 1<\/mml:mn>&#x2212;<\/mml:mo>O<\/mml:mi>(<\/mml:mo>2<\/mml:mn>&#x2212;<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>, which confirms a variant of a conjecture by Aaronson and Chen.<\/jats:p>","DOI":"10.22331\/q-2025-10-13-1883","type":"journal-article","created":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T10:33:31Z","timestamp":1760351611000},"page":"1883","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":4,"title":["On the average-case complexity of learning output distributions of quantum circuits"],"prefix":"10.22331","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6685-8400","authenticated-orcid":false,"given":"Alexander","family":"Nietner","sequence":"first","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Germany"}]},{"given":"Marios","family":"Ioannou","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Germany"}]},{"given":"Ryan","family":"Sweke","sequence":"additional","affiliation":[{"name":"IBM Quantum, Almaden Research Center, San Jose, CA 95120, USA"}]},{"given":"Richard","family":"Kueng","sequence":"additional","affiliation":[{"name":"Institute for Integrated Circuits, Department of Computer Science, Johannes Kepler University Linz, Austria"}]},{"given":"Jens","family":"Eisert","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4174-5706","authenticated-orcid":false,"given":"Marcel","family":"Hinsche","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Germany"}]},{"given":"Jonas","family":"Haferkamp","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Germany"},{"name":"School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02318, USA"},{"name":"Department of Mathematics, Saarland University, Saarbr\u00fccken, Germany"}]}],"member":"9598","published-online":{"date-parts":[[2025,10,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Anurag Anshuand Srinivasan Arunachalam ``A Survey on the Complexity of Learning Quantum States'' Nature Reviews Physics 6, 59-69 (2024).","DOI":"10.1038\/s42254-023-00662-4"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Naman Agarwal, Pranjal Awasthi, and Satyen Kale, ``A Deep Conditioning Treatment of Neural Networks'' Proceedings of the 32nd International Conference on Algorithmic Learning Theory 132, 249\u2013305 (2021).","DOI":"10.48550\/arXiv.2002.01523"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Scott Aaronson ``The learnability of quantum states'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 463, 3089\u20133114 (2007).","DOI":"10.1098\/rspa.2007.0113"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Sanjeev Arora, Aditya Bhaskara, Rong Ge, and Tengyu Ma, ``Provable Bounds for Learning Some Deep Representations'' Proceedings of the 31st International Conference on Machine Learning 32, 584\u2013592 (2014).","DOI":"10.48550\/arXiv.1310.6343"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Scott Aaronsonand Lijie Chen ``Complexity-theoretic foundations of quantum supre-macy experiments'' 32nd Computational Complexity Conference (CCC 2017) 79, 22:1\u201322:67 (2017).","DOI":"10.4230\/LIPIcs.CCC.2017.22"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalamand Ronald de Wolf ``Guest Column: A Survey of Quantum Learning Theory'' SIGACT News 48, 41\u201367 (2017).","DOI":"10.1145\/3106700.3106710"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Scott Aaronsonand Daniel Gottesman ``Improved simulation of stabilizer circuits'' Phys. Rev. A 70 (2004).","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalam, Alex Bredariol Grilo, and Aarthi Sundaram, ``Quantum Hardness of Learning Shallow Classical Circuits'' SIAM Journal on Computing 50, 972\u20131013 (2021) doi: 10.1137\/20M1344202.","DOI":"10.1137\/20M1344202"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalam, Alex B. Grilo, and Henry Yuen, ``Quantum statistical query learning'' (2020).","DOI":"10.48550\/arXiv.2002.08240"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalam, Vojt\u011bch Havl\u00ed\u010dek, and Louis Schatzki, ``On the role of entanglement and statistics in learning'' Proceedings of the 37th International Conference on Neural Information Processing Systems (2023).","DOI":"10.48550\/arXiv.2306.03161"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Eddie Aamariand Alexander Knop ``Statistical query complexity of manifold estimation'' Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 116\u2013122 (2021).","DOI":"10.1145\/3406325.3451135"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Eric R. Anschuetzand Bobak T. Kiani ``Quantum variational algorithms are swamped with traps'' Nature Communications 13 (2022).","DOI":"10.1038\/s41467-022-35364-5"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Emmanuel Abbeand Colin Sandon ``Polynomial-time universality and limitations of deep learning'' Communications on Pure and Applied Mathematics 76, 3493\u20133549 (2023) doi: 10.1002\/cpa.22121.","DOI":"10.1002\/cpa.22121"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Boaz Barak ``The Complexity of Public-Key Cryptography'' Springer International Publishing (2017).","DOI":"10.1007\/978-3-319-57048-8_2"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Boaz Barak, Chi-Ning Chou, and Xun Gao, ``Spoofing linear cross-entropy benchmarking in shallow quantum circuits'' 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 185, 30:1\u201330:20 (2021).","DOI":"10.4230\/LIPIcs.ITCS.2021.30"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Fernando G. S. L. Brand\u00e3o, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill, ``Models of quantum complexity growth'' PRX Quantum 2 (2021).","DOI":"10.1103\/PRXQuantum.2.030316"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim, ``Practical privacy: The SuLQ framework'' Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems - PODS '05 128 (2005).","DOI":"10.1145\/1065167.1065184"},{"key":"17","unstructured":"Ben ``Solve the limit of the sucession $ \\left(1+\\frac{1}{2}\\right) \\left(1+\\frac{1}{4}\\right) \\times \\dots \\times \\left(1+\\frac{1}{2^n}\\right) $'' Mathematics Stack Exchange (2021)."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Bonnie Berger ``The Fourth Moment Method'' SIAM Journal on Computing 26 (1997).","DOI":"10.1137\/S0097539792240005"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich, ``Weakly learning DNF and characterizing statistical query learning using Fourier analysis'' Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing (1994).","DOI":"10.1145\/195058.195147"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Avrim Blum, Merrick Furst, Michael Kearns, and Richard J. Lipton, ``Cryptographic Primitives Based on Hard Learning Problems'' Advances in Cryptology \u2014 CRYPTO' 93 278\u2013291 (1994).","DOI":"10.1007\/3-540-48329-2_24"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Fernando G. S. L. Brandao, Aram W. Harrow, and Micha\u0142 Horodecki, ``Local random quantum circuits are approximate polynomial-designs'' Communications in Mathematical Physics 346, 397\u2013434 (2016).","DOI":"10.1007\/s00220-016-2706-8"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd, ``Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459\u2013472 (2011).","DOI":"10.1098\/rspa.2010.0301"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, and Amanda Askell, ``Language models are few-shot learners'' Advances in neural information processing systems 33, 1877\u20131901 (2020).","DOI":"10.48550\/arXiv.2005.14165"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd, ``Achieving quantum supremacy with sparse and noisy commuting quantum computations'' Quantum 1, 8 (2017).","DOI":"10.22331\/q-2017-04-25-8"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Anna Choromanska, Mikael Henaff, Michael Mathieu, Gerard Ben Arous, and Yann LeCun, ``The Loss Surfaces of Multilayer Networks'' Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics 38, 192\u2013204 (2015).","DOI":"10.48550\/arXiv.1412.0233"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Sitan Chen, Jerry Li, and Yuanzhi Li, ``Learning (very) simple generative models is hard'' Proceedings of the 36th International Conference on Neural Information Processing Systems (2022).","DOI":"10.48550\/arXiv.2205.16003"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Brian Coyle, Daniel Mills, Vincent Danos, and Elham Kashefi, ``The Born supremacy: Quantum advantage and training of an Ising born machine'' npj Quantum Information 6, 1\u201311 (2020).","DOI":"10.1038\/s41534-020-00288-9"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Christoph Dankert ``Efficient simulation of random quantum states and operators'' arXiv (2005).","DOI":"10.48550\/arXiv.quant-ph\/0512217"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Amit Daniely ``SGD Learns the conjugate kernel class of the network'' Proceedings of the 31st International Conference on Neural Information Processing Systems 2419\u20132427 (2017).","DOI":"10.48550\/arXiv.1702.08503"},{"key":"30","doi-asserted-by":"publisher","unstructured":"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) 73\u201384 (2017).","DOI":"10.1109\/FOCS.2017.16"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith, ``Calibrating noise to sensitivity in private data analysis'' Theory of Cryptography 265\u2013284 (2006).","DOI":"10.1007\/11681878_14"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Amit Danielyand Gal Vardi ``Hardness of learning neural networks with natural weights'' Proceedings of the 34th International Conference on Neural Information Processing Systems 930\u2013940 (2020).","DOI":"10.48550\/arXiv.2006.03177"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Vitaly Feldman ``Evolvability from learning algorithms'' Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing 619\u2013628 (2008).","DOI":"10.1145\/1374376.1374465"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Vitaly Feldman ``A General Characterization of the Statistical Query Complexity'' Proceedings of the 2017 Conference on Learning Theory 65 (2017).","DOI":"10.48550\/arXiv.1608.02198"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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, 1\u201337 (2017).","DOI":"10.1145\/3046674"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Vitaly Feldman, Crist\u00f3bal Guzm\u00e1n, and Santosh Vempala, ``Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization'' Mathematics of Operations Research 46, 912\u2013945 (2021).","DOI":"10.1287\/moor.2020.1111"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Vitaly Feldman, Will Perkins, and Santosh Vempala, ``On the Complexity of Random Satisfiability Problems with Planted Solutions'' SIAM Journal on Computing 47, 1294\u20131338 (2018).","DOI":"10.1137\/16M1078471"},{"key":"38","doi-asserted-by":"publisher","unstructured":"David Gross, Koenraad Audenaert, and Jens Eisert, ``Evenly distributed unitaries: On the structure of unitary designs'' Journal of Mathematical Physics 48, 052104 (2007).","DOI":"10.1063\/1.2716992"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman ``The Heisenberg representation of quantum computers'' (1998).","DOI":"10.48550\/arXiv.quant-ph\/9807006"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio, ``Generative adversarial nets'' Advances in neural information processing systems 2672\u20132680 (2014).","DOI":"10.48550\/arXiv.1406.2661"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Jonas Haferkamp ``Random quantum circuits are approximate unitary $t$-designs in depth $O\\left(nt^{5+o(1)}\\right)$'' Quantum 6, 795 (2022).","DOI":"10.22331\/q-2022-09-08-795"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow ``The church of the symmetric subspace'' (2013).","DOI":"10.48550\/arXiv.1308.6595"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack W. Rae, and Laurent Sifre, ``Training compute-optimal large language models'' arXiv (2022).","DOI":"10.48550\/arXiv.2203.15556"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Dominik Hangleiterand Jens Eisert ``Computational advantage of quantum random sampling'' (2022).","DOI":"10.48550\/arXiv.2206.04079"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Jonas Haferkampand Nicholas Hunter-Jones ``Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions'' Physical Review A 104, 022417 (2021).","DOI":"10.1103\/PhysRevA.104.022417"},{"key":"46","doi-asserted-by":"publisher","unstructured":"M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, and R. Sweke, ``One $T$ Gate Makes Distribution Learning Hard'' Phys. Rev. Lett. 130, 240602 (2023).","DOI":"10.1103\/PhysRevLett.130.240602"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Aram W. Harrowand Richard A. Low ``Random quantum circuits are approximate 2-designs'' Communications in Mathematical Physics 291, 257\u2013302 (2009).","DOI":"10.1007\/s00220-009-0873-6"},{"key":"48","doi-asserted-by":"publisher","unstructured":"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 (2024).","DOI":"10.1145\/3618260.3649722"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Nicholas Hunter-Jones ``Unitary designs from statistical mechanics in random quantum circuits'' (2019).","DOI":"10.48550\/ARXIV.1905.12053"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Russell Impagliazzoand Leonid A. Levin ``No better ways to generate hard NP instances than picking uniformly at random'' Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science 812\u2013821 vol.2 (1990).","DOI":"10.1109\/FSCS.1990.89604"},{"key":"51","doi-asserted-by":"publisher","unstructured":"John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin \u017d\u00eddek, and Anna Pota-penko, ``Highly accurate protein structure prediction with AlphaFold'' Nature 596, 583\u2013589 (2021).","DOI":"10.1038\/s41586-021-03819-2"},{"key":"52","doi-asserted-by":"publisher","unstructured":"Majid Janzamin, Hanie Sedghi, and Anima Anandkumar, ``Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods'' (2016).","DOI":"10.48550\/arXiv.1506.08473"},{"key":"53","doi-asserted-by":"publisher","unstructured":"Michael Kearns ``Efficient Noise-Tolerant Learning from Statistical Queries'' Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing 392\u2013401 (1993).","DOI":"10.1145\/167088.167200"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Richard Kuengand David Gross ``Qubit stabilizer states are complex projective 3-designs'' (2015).","DOI":"10.48550\/arXiv.1510.02767"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Michael Kharitonov ``Cryptographic hardness of distribution-specific learning'' Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing 372\u2013381 (1993).","DOI":"10.1145\/167088.167197"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith, ``What can we learn privately?'' SIAM Journal on Computing 40 (2011).","DOI":"10.1137\/090756090"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Michael J. Kearns, Yishay Mansour, D. Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie, ``On the learnability of discrete distributions'' Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing 273\u2013282 (1994).","DOI":"10.1145\/195058.195155"},{"key":"58","doi-asserted-by":"publisher","unstructured":"Stefan Knabe ``Energy gaps and elementary excitations for certain VBS-quantum antiferromagnets'' Journal of Statistical Physics 52, 627\u2013638 (1988).","DOI":"10.1007\/BF01019721"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Michael J. Kearnsand Umesh Vazirani ``An Introduction to Computational Learning Theory'' The MIT Press (1994).","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"60","doi-asserted-by":"publisher","unstructured":"Zeph Landauand Yunchao Liu ``Learning Quantum States Prepared by Shallow Circuits in Polynomial Time'' Proceedings of the 57th Annual ACM Symposium on Theory of Computing 1828\u20131838 (2025).","DOI":"10.1145\/3717823.3718311"},{"key":"61","doi-asserted-by":"publisher","unstructured":"Nathan Linial, Yishay Mansour, and Noam Nisan, ``Constant depth circuits, Fourier transform, and learnability'' J. ACM 40, 607\u2013620 (1993).","DOI":"10.1145\/174130.174138"},{"key":"62","doi-asserted-by":"publisher","unstructured":"Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir, ``On the Computational Efficiency of Training Neural Networks'' Advances in Neural Information Processing Systems 27 (2014).","DOI":"10.48550\/arXiv.1410.1141"},{"key":"63","doi-asserted-by":"publisher","unstructured":"Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii, ``Quantum circuit Learning'' Physical Review A 98, 032309 (2018) arXiv:1803.00745.","DOI":"10.1103\/PhysRevA.98.032309"},{"key":"64","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro ``Learning stabilizer states by Bell sampling'' (2017).","DOI":"10.48550\/arXiv.1707.04012"},{"key":"65","doi-asserted-by":"publisher","unstructured":"Bruno Nachtergaele ``The spectral gap for some spin chains with discrete symmetry breaking'' Communications in Mathematical Physics 175, 565\u2013606 (1996).","DOI":"10.1007\/BF02099509"},{"key":"66","unstructured":"Mikito Nanashima ``A theory of heuristic learnability'' Proceedings of Thirty Fourth Conference on Learning Theory 3483\u20133525 (2021) optissn: 2640-3498."},{"key":"67","doi-asserted-by":"publisher","unstructured":"Alexander Nietner ``Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms'' (2023).","DOI":"10.48550\/arXiv.2310.17716"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran, ``Evaluating analytic gradients on quantum hardware'' Physical Review A 99, 032331 (2019) arXiv:1811.11184.","DOI":"10.1103\/PhysRevA.99.032331"},{"key":"69","doi-asserted-by":"publisher","unstructured":"Ohad Shamir ``Distribution-Specific Hardness of Learning Neural Networks'' Journal of Machine Learning Research 19, 1\u201329 (2018).","DOI":"10.48550\/arXiv.1609.01037"},{"key":"70","unstructured":"James C. Spall ``An overview of the simultaneous perturbation method for efficient optimization'' Johns Hopkins APL Technical Digest 19, 11 (1998)."},{"key":"71","unstructured":"Jacob Steinhardt, Gregory Valiant, and Stefan Wager, ``Memory, Communication, and Statistical Queries'' 29th Annual Conference on Learning Theory 49, 1490\u20131516 (2016)."},{"key":"72","doi-asserted-by":"publisher","unstructured":"Barbara M. Terhaland David P. DiVincenzo ``Classical simulation of noninteracting-fermion quantum circuits'' Physical Review A 65, 032325 (2002).","DOI":"10.1103\/PhysRevA.65.032325"},{"key":"73","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant ``Evolvability'' Journal of the ACM 56, 1\u201321 (2009).","DOI":"10.1145\/1462153.1462156"},{"key":"74","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant ``Quantum circuits that can be simulated classically in polynomial time'' SIAM Journal on Computing (2012).","DOI":"10.1137\/S0097539700377025"},{"key":"75","doi-asserted-by":"publisher","unstructured":"Leslie G. Valiant ``A theory of the learnable'' Proceedings of the sixteenth annual ACM symposium on Theory of computing 436\u2013445 (1984).","DOI":"10.1145\/800057.808710"},{"key":"76","doi-asserted-by":"publisher","unstructured":"Chirag Wadhwaand Mina Doosti ``Learning Quantum Processes with Quantum Statistical Queries'' Quantum 9, 1739 (2025).","DOI":"10.22331\/q-2025-05-12-1739"},{"key":"77","doi-asserted-by":"publisher","unstructured":"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 Quantum 5, 040306 (2024).","DOI":"10.1103\/PRXQuantum.5.040306"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-13-1883\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T10:33:36Z","timestamp":1760351616000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-10-13-1883\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,13]]},"references-count":78,"URL":"https:\/\/doi.org\/10.22331\/q-2025-10-13-1883","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,13]]},"article-number":"1883"}}