{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T02:00:13Z","timestamp":1772157613553,"version":"3.50.1"},"reference-count":100,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T00:00:00Z","timestamp":1768867200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"DARPA ONISQ","award":["W911NF2010021"],"award-info":[{"award-number":["W911NF2010021"]}]},{"name":"NSF PFC","award":["PHYS 2317149"],"award-info":[{"award-number":["PHYS 2317149"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Recent theoretical results in quantum machine learning have demonstrated a general trade-off between the expressive power of quantum neural networks (QNNs) and their trainability; as a corollary of these results, practical exponential separations in expressive power over classical machine learning models are believed to be infeasible as such QNNs take a time to train that is exponential in the model size. We here circumvent these negative results by constructing a hierarchy of efficiently trainable QNNs that exhibit unconditionally provable, polynomial memory separations of arbitrary constant degree over classical neural networks\u2014including state-of-the-art models, such as Transformers\u2014in performing a classical sequence modeling task. This construction is also computationally efficient, as each unit cell of the introduced class of QNNs only has constant gate complexity. We show that contextuality\u2014informally, a quantitative notion of semantic ambiguity\u2014is the source of the expressivity separation, suggesting that other learning tasks with this property may be a natural setting for the use of quantum learning algorithms.<\/jats:p>","DOI":"10.22331\/q-2026-01-20-1976","type":"journal-article","created":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T11:53:17Z","timestamp":1768909997000},"page":"1976","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Arbitrary Polynomial Separations in Trainable Quantum Machine Learning"],"prefix":"10.22331","volume":"10","author":[{"given":"Eric R.","family":"Anschuetz","sequence":"first","affiliation":[{"name":"Institute for Quantum Information and Matter, Caltech, Pasadena, CA, USA"},{"name":"Walter Burke Institute for Theoretical Physics, Caltech, Pasadena, CA, USA"},{"name":"MIT Center for Theoretical Physics, Cambridge, MA, USA"}]},{"given":"Xun","family":"Gao","sequence":"additional","affiliation":[{"name":"JILA and Department of Physics, CU Boulder, Boulder, CO, USA"}]}],"member":"9598","published-online":{"date-parts":[[2026,1,20]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"F. Arute et al., ``Quantum supremacy using a programmable superconducting processor,'' Nature 574, 505 (2019).","DOI":"10.1038\/s41586-019-1666-5"},{"key":"1","doi-asserted-by":"publisher","unstructured":"H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, et al., ``Quantum computational advantage using photons,'' Science 370, 1460 (2020).","DOI":"10.1126\/science.abe8770"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, et al., ``Strong quantum computational advantage using a superconducting quantum processor,'' Phys. Rev. Lett. 127, 180501 (2021).","DOI":"10.1103\/PhysRevLett.127.180501"},{"key":"3","doi-asserted-by":"publisher","unstructured":"H.-S. Zhong, Y.-H. Deng, J. Qin, H. Wang, M.-C. Chen, L.-C. Peng, Y.-H. Luo, D. Wu, S.-Q. Gong, H. Su, et al., ``Phase-programmable Gaussian boson sampling using stimulated squeezed light,'' Phys. Rev. Lett. 127, 180502 (2021).","DOI":"10.1103\/PhysRevLett.127.180502"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, et al., ``Quantum computational advantage via 60-qubit 24-cycle random circuit sampling,'' Sci. Bull. 67, 240 (2022).","DOI":"10.1016\/j.scib.2021.10.017"},{"key":"5","doi-asserted-by":"publisher","unstructured":"D. Hangleiter and J. Eisert, ``Computational advantage of quantum random sampling,'' (2022), arXiv:2206.04079 [quant-ph].","DOI":"10.1103\/RevModPhys.95.035001"},{"key":"6","doi-asserted-by":"publisher","unstructured":"S. Aaronson and A. Arkhipov, ``The computational complexity of linear optics,'' in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11 (Association for Computing Machinery, New York, NY, USA, 2011) pp. 333\u2013342.","DOI":"10.1145\/1993636.1993682"},{"key":"7","doi-asserted-by":"publisher","unstructured":"A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, ``On the complexity and verification of quantum random circuit sampling,'' Nat. Phys. 15, 159 (2019).","DOI":"10.1038\/s41567-018-0318-2"},{"key":"8","doi-asserted-by":"publisher","unstructured":"S. Aaronson and S. Gunn, ``On the classical hardness of spoofing linear cross-entropy benchmarking,'' Theory Comput. 16, 1 (2020).","DOI":"10.4086\/toc.2020.v016a011"},{"key":"9","doi-asserted-by":"publisher","unstructured":"M. Schuld, I. Sinayskiy, and F. Petruccione, ``An introduction to quantum machine learning,'' Contemp. Phys. 56, 172 (2015).","DOI":"10.1080\/00107514.2014.964942"},{"key":"10","doi-asserted-by":"publisher","unstructured":"J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, ``Quantum machine learning,'' Nature 549, 195 (2017).","DOI":"10.1038\/nature23474"},{"key":"11","doi-asserted-by":"publisher","unstructured":"M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko, ``Quantum Boltzmann machine,'' Phys. Rev. X 8, 021050 (2018).","DOI":"10.1103\/PhysRevX.8.021050"},{"key":"12","doi-asserted-by":"publisher","unstructured":"S. Lloyd and C. Weedbrook, ``Quantum generative adversarial learning,'' Phys. Rev. Lett. 121, 040502 (2018).","DOI":"10.1103\/PhysRevLett.121.040502"},{"key":"13","doi-asserted-by":"publisher","unstructured":"M. Schuld and N. Killoran, ``Quantum machine learning in feature Hilbert spaces,'' Phys. Rev. Lett. 122, 040504 (2019).","DOI":"10.1103\/PhysRevLett.122.040504"},{"key":"14","doi-asserted-by":"publisher","unstructured":"N. Killoran, T. R. Bromley, J. M. Arrazola, M. Schuld, N. Quesada, and S. Lloyd, ``Continuous-variable quantum neural networks,'' Phys. Rev. Research 1, 033063 (2019).","DOI":"10.1103\/PhysRevResearch.1.033063"},{"key":"15","doi-asserted-by":"publisher","unstructured":"X. Gao, Z.-Y. Zhang, and L.-M. Duan, ``A quantum machine learning algorithm based on generative models,'' Sci. Adv. 4, eaat9004 (2018).","DOI":"10.1126\/sciadv.aat9004"},{"key":"16","doi-asserted-by":"publisher","unstructured":"B. Coyle, D. Mills, V. Danos, and E. Kashefi, ``The Born supremacy: quantum advantage and training of an Ising Born machine,'' npj Quantum Inf. 6, 1 (2020).","DOI":"10.1038\/s41534-020-00288-9"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Y. Du, M.-H. Hsieh, T. Liu, and D. Tao, ``Expressive power of parametrized quantum circuits,'' Phys. Rev. Research 2, 033125 (2020).","DOI":"10.1103\/PhysRevResearch.2.033125"},{"key":"18","doi-asserted-by":"publisher","unstructured":"R. Sweke, J.-P. Seifert, D. Hangleiter, and J. Eisert, ``On the Quantum versus Classical Learnability of Discrete Distributions,'' Quantum 5, 417 (2021).","DOI":"10.22331\/q-2021-03-23-417"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Y. Liu, S. Arunachalam, and K. Temme, ``A rigorous and robust quantum speed-up in supervised machine learning,'' Nat. Phys. 17, 1013 (2021).","DOI":"10.1038\/s41567-021-01287-z"},{"key":"20","unstructured":"E. Gil-Fuster, C. Gyurik, A. P\u00e9rez-Salinas, and V. Dunjko, ``On the relation between trainability and dequantization of variational quantum learning models,'' (2024), arXiv:2406.07072 [quant-ph]."},{"key":"21","doi-asserted-by":"publisher","unstructured":"P. W. Shor, ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,'' SIAM J. Comput. 26, 1484 (1997).","DOI":"10.1137\/S0097539795293172"},{"key":"22","unstructured":"A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y. LeCun, ``The loss surfaces of multilayer networks,'' in Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 38, edited by G. Lebanon and S. V. N. Vishwanathan (PMLR, San Diego, CA, USA, 2015) pp. 192\u2013204."},{"key":"23","unstructured":"P. A. Chaudhari, A Picture of the Energy Landscape of Deep Neural Networks, Ph.D. thesis, University of California, Los Angeles (2018)."},{"key":"24","doi-asserted-by":"publisher","unstructured":"J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, ``Barren plateaus in quantum neural network training landscapes,'' Nat. Commun. 9, 4812 (2018).","DOI":"10.1038\/s41467-018-07090-4"},{"key":"25","doi-asserted-by":"publisher","unstructured":"M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, ``Cost function dependent barren plateaus in shallow parametrized quantum circuits,'' Nat. Commun. 12, 1791 (2021).","DOI":"10.1038\/s41467-021-21728-w"},{"key":"26","unstructured":"J. Napp, ``Quantifying the barren plateau phenomenon for a model of unstructured variational ans\u00e4tze,'' (2022), arXiv:2203.06174 [quant-ph]."},{"key":"27","doi-asserted-by":"publisher","unstructured":"M. Cerezo and P. J. Coles, ``Higher order derivatives of quantum neural networks with barren plateaus,'' Quantum Sci. Technol. 6, 035006 (2021).","DOI":"10.1088\/2058-9565\/abf51a"},{"key":"28","doi-asserted-by":"publisher","unstructured":"A. Arrasmith, M. Cerezo, P. Czarnik, L. Cincio, and P. J. Coles, ``Effect of barren plateaus on gradient-free optimization,'' Quantum 5, 558 (2021).","DOI":"10.22331\/q-2021-10-05-558"},{"key":"29","unstructured":"E. R. Anschuetz, ``Critical points in quantum generative models,'' in International Conference on Learning Representations, edited by K. Hofmann, A. Rush, Y. Liu, C. Finn, Y. Choi, and M. Deisenroth (OpenReview, 2022)."},{"key":"30","doi-asserted-by":"publisher","unstructured":"E. R. Anschuetz and B. T. Kiani, ``Quantum variational algorithms are swamped with traps,'' Nat. Commun. 13, 7760 (2022).","DOI":"10.1038\/s41467-022-35364-5"},{"key":"31","unstructured":"E. R. Anschuetz, ``A unified theory of quantum neural network loss landscapes,'' (2024), arXiv:2408.11901 [quant-ph]."},{"key":"32","doi-asserted-by":"publisher","unstructured":"E. Fontana, D. Herman, S. Chakrabarti, N. Kumar, R. Yalovetzky, J. Heredge, S. H. Sureshbabu, and M. Pistoia, ``The adjoint is all you need: Characterizing barren plateaus in quantum ans\u00e4tze,'' (2023), arXiv:2309.07902 [quant-ph].","DOI":"10.1038\/s41467-024-49910-w"},{"key":"33","doi-asserted-by":"publisher","unstructured":"M. Ragone, B. N. Bakalov, F. Sauvage, A. F. Kemper, C. O. Marrero, M. Larocca, and M. Cerezo, ``A Lie algebraic theory of barren plateaus for deep parameterized quantum circuits. Nat Commun 15, 7172 (2024), arXiv:2309.09342 [quant-ph].","DOI":"10.1038\/s41467-024-49909-3"},{"key":"34","doi-asserted-by":"publisher","unstructured":"E. R. Anschuetz, A. Bauer, B. T. Kiani, and S. Lloyd, ``Efficient classical algorithms for simulating symmetric quantum systems,'' Quantum 7, 1189 (2023a).","DOI":"10.22331\/q-2023-11-28-1189"},{"key":"35","doi-asserted-by":"publisher","unstructured":"M. L. Goh, M. Larocca, L. Cincio, M. Cerezo, and F. Sauvage, ``Lie-algebraic classical simulations for quantum computing,'' Phys. Rev. Res. 7, 033266 (2025).","DOI":"10.1103\/3y65-f5w6"},{"key":"36","doi-asserted-by":"publisher","unstructured":"M. Cerezo, M. Larocca, D. Garc\u00eda-Mart\u00edn, N. L. Diaz, P. Braccia, E. Fontana, M. S. Rudolph, P. Bermejo, A. Ijaz, S. Thanasilp, E. R. Anschuetz, and Z. Holmes, ``Does provable absence of barren plateaus imply classical simulability?'' Nat. Commun. 16, 7907 (2025).","DOI":"10.1038\/s41467-025-63099-6"},{"key":"37","doi-asserted-by":"publisher","unstructured":"X. Gao, E. R. Anschuetz, S.-T. Wang, J. I. Cirac, and M. D. Lukin, ``Enhancing generative models via quantum correlations,'' Phys. Rev. X 12, 021037 (2022).","DOI":"10.1103\/PhysRevX.12.021037"},{"key":"38","doi-asserted-by":"publisher","unstructured":"H. Zhao and D.-L. Deng, ``Entanglement-induced provable and robust quantum learning advantages,'' (2024), arXiv:2410.03094 [quant-ph].","DOI":"10.1038\/s41534-025-01078-x"},{"key":"39","doi-asserted-by":"publisher","unstructured":"E. R. Anschuetz, H.-Y. Hu, J.-L. Huang, and X. Gao, ``Interpretable quantum advantage in neural sequence learning,'' PRX Quantum 4, 020338 (2023b).","DOI":"10.1103\/PRXQuantum.4.020338"},{"key":"40","doi-asserted-by":"publisher","unstructured":"R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, and H. Neven, ``Focus beyond quadratic speedups for error-corrected quantum advantage,'' PRX Quantum 2, 010103 (2021).","DOI":"10.1103\/PRXQuantum.2.010103"},{"key":"41","unstructured":"A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, ``Attention is all you need,'' in Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, edited by I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Curran Associates, Inc., Red Hook, NY, USA, 2017) pp. 6000\u20136010."},{"key":"42","doi-asserted-by":"publisher","unstructured":"Y. Takeuchi, A. Mantri, T. Morimae, A. Mizutani, and J. F. Fitzsimons, ``Resource-efficient verification of quantum computing using serfling\u2019s bound,'' npj Quantum Inf. 5, 27 (2019).","DOI":"10.1038\/s41534-019-0142-2"},{"key":"43","doi-asserted-by":"publisher","unstructured":"M. A. Webster, B. J. Brown, and S. D. Bartlett, ``The XP stabiliser formalism: a generalisation of the Pauli stabiliser formalism with arbitrary phases,'' Quantum 6, 815 (2022).","DOI":"10.22331\/q-2022-09-22-815"},{"key":"44","doi-asserted-by":"publisher","unstructured":"R. Somma, H. Barnum, G. Ortiz, and E. Knill, ``Efficient solvability of Hamiltonians and limits on the power of some quantum computational models,'' Phys. Rev. Lett. 97, 190501 (2006).","DOI":"10.1103\/PhysRevLett.97.190501"},{"key":"45","unstructured":"M. Mints and E. R. Anschuetz, ``Fragmentation is efficiently learnable by quantum neural networks,'' (2025), arXiv:2512.00751 [quant-ph]."},{"key":"46","unstructured":"C.-J. Wu, R. Raghavendra, U. Gupta, B. Acun, N. Ardalani, K. Maeng, G. Chang, F. Aga, J. Huang, C. Bai, M. Gschwind, A. Gupta, M. Ott, A. Melnikov, S. Candido, D. Brooks, G. Chauhan, B. Lee, H.-H. Lee, B. Akyildiz, M. Balandat, J. Spisak, R. Jain, M. Rabbat, and K. Hazelwood, ``Sustainable AI: Environmental implications, challenges and opportunities,'' in Proceedings of Machine Learning and Systems, Vol. 4, edited by D. Marculescu, Y. Chi, and C. Wu (2022) pp. 795\u2013813."},{"key":"47","unstructured":"I. Mavromatis, K. Katsaros, and A. Khan, ``Computing within limits: An empirical study of energy consumption in ML training and inference,'' (2024), arXiv:2406.14328 [cs.LG]."},{"key":"48","doi-asserted-by":"crossref","unstructured":"S. Kochen and E. P. Specker, ``The problem of hidden variables in quantum mechanics,'' J. Math. Mech. 17, 59 (1967).","DOI":"10.1512\/iumj.1967.17.17004"},{"key":"49","doi-asserted-by":"publisher","unstructured":"S. Abramsky and A. Brandenburger, ``The sheaf-theoretic structure of non-locality and contextuality,'' New J. Phys. 13, 113036 (2011).","DOI":"10.1088\/1367-2630\/13\/11\/113036"},{"key":"50","doi-asserted-by":"publisher","unstructured":"S. Abramsky and M. Sadrzadeh, ``Semantic unification,'' in Categories and Types in Logic, Language, and Physics: Essays Dedicated to Jim Lambek on the Occasion of His 90th Birthday, edited by C. Casadio, B. Coecke, M. Moortgat, and P. Scott (Springer Berlin Heidelberg, Berlin, Heidelberg, Germany, 2014) pp. 1\u201313.","DOI":"10.1007\/978-3-642-54789-8_1"},{"key":"51","doi-asserted-by":"publisher","unstructured":"S. Abramsky, ``Contextual semantics: From quantum mechanics to logic, databases, constraints, and complexity,'' in Contextuality from Quantum Physics to Psychology (World Scientific Publishing, 2016) Chap. Chapter 2, pp. 23\u201350.","DOI":"10.1142\/9789814730617_0002"},{"key":"52","doi-asserted-by":"publisher","unstructured":"S. Abramsky, R. Soares Barbosa, K. Kishida, R. Lal, and S. Mansfield, ``Contextuality, cohomology and paradox,'' in 24th EACSL Annual Conference on Computer Science Logic (CSL 2015), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 41, edited by S. Kreutzer (Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 2015) pp. 211\u2013228.","DOI":"10.4230\/LIPIcs.CSL.2015.211"},{"key":"53","doi-asserted-by":"publisher","unstructured":"V. H. Cervantes and E. N. Dzhafarov, ``Contextuality analysis of impossible figures,'' Entropy 22, 981 (2020).","DOI":"10.3390\/e22090981"},{"key":"54","doi-asserted-by":"publisher","unstructured":"R. Raz, ``Exponential separation of quantum and classical communication complexity,'' in Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, STOC '99 (Association for Computing Machinery, New York, NY, USA, 1999) pp. 358\u2013367.","DOI":"10.1145\/301250.301343"},{"key":"55","doi-asserted-by":"publisher","unstructured":"H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, ``Quantum fingerprinting,'' Phys. Rev. Lett. 87, 167902 (2001).","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"56","doi-asserted-by":"publisher","unstructured":"F. Le Gall, ``Exponential separation of quantum and classical online space complexity,'' in Proceedings of the Eighteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '06, edited by P. B. Gibbons and U. Vishkin (Association for Computing Machinery, New York, NY, USA, 2006) pp. 67\u201373.","DOI":"10.1145\/1148109.1148119"},{"key":"57","doi-asserted-by":"publisher","unstructured":"D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf, ``Exponential separations for one-way quantum communication complexity, with applications to cryptography,'' in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07, edited by D. Johnson and U. Feige (Association for Computing Machinery, New York, NY, USA, 2007) pp. 516\u2013525.","DOI":"10.1145\/1250790.1250866"},{"key":"58","doi-asserted-by":"publisher","unstructured":"S. Gupta, D. Saha, Z.-P. Xu, A. Cabello, and A. S. Majumdar, ``Quantum contextuality provides communication complexity advantage,'' Phys. Rev. Lett. 130, 080802 (2023).","DOI":"10.1103\/PhysRevLett.130.080802"},{"key":"59","doi-asserted-by":"crossref","unstructured":"J. Kallaugher, O. Parekh, and N. Voronova, ``Exponential quantum space advantage for approximating maximum directed cut in the streaming model,'' (2023), arXiv:2311.14123 [quant-ph].","DOI":"10.1145\/3618260.3649709"},{"key":"60","doi-asserted-by":"publisher","unstructured":"S. Manna, A. Chaturvedi, and D. Saha, ``Unbounded quantum advantage in communication complexity measured by distinguishability,'' (2024), arXiv:2401.12903 [quant-ph].","DOI":"10.1103\/PhysRevResearch.6.043269"},{"key":"61","doi-asserted-by":"publisher","unstructured":"M. S. Rudolph, S. Lerch, S. Thanasilp, O. Kiss, S. Vallecorsa, M. Grossi, and Z. Holmes, ``Trainability barriers and opportunities in quantum generative modeling,'' (2023), arXiv:2305.02881 [quant-ph].","DOI":"10.1038\/s41534-024-00902-0"},{"key":"62","unstructured":"I. Sutskever, O. Vinyals, and Q. V. Le, ``Sequence to sequence learning with neural networks,'' in Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS'14, edited by Z. Ghahramani, M. Welling, C. Cortes, and N. Lawrence (Curran Associates, Inc., Red Hook, NY, USA, 2014) pp. 3104\u20133112."},{"key":"63","doi-asserted-by":"publisher","unstructured":"R. Prabhavalkar, K. Rao, T. N. Sainath, B. Li, L. Johnson, and N. Jaitly, ``A comparison of sequence-to-sequence models for speech recognition,'' in Proc. Interspeech 2017, edited by F. Lacerda (Curran Associates, Inc., Red Hook, NY, USA, 2017) pp. 939\u2013943.","DOI":"10.21437\/Interspeech.2017-233"},{"key":"64","doi-asserted-by":"publisher","unstructured":"O. Vinyals, A. Toshev, S. Bengio, and D. Erhan, ``Show and tell: A neural image caption generator,'' in 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), edited by K. Barnard, H. Bischof, P. Felzenszwalb, D. Forsyth, S. Lazebnik, and J. Matas (Curran Associates, Inc., Red Hook, NY, USA, 2015) pp. 3156\u20133164.","DOI":"10.1109\/CVPR.2015.7298935"},{"key":"65","doi-asserted-by":"publisher","unstructured":"J. J. Hopfield, ``Neural networks and physical systems with emergent collective computational abilities,'' Proc. Natl. Acad. Sci. U.S.A. 79, 2554 (1982).","DOI":"10.1073\/pnas.79.8.2554"},{"key":"66","doi-asserted-by":"publisher","unstructured":"S. Hochreiter and J. Schmidhuber, ``Long short-term memory,'' Neural Comput. 9, 1735 (1997).","DOI":"10.1162\/neco.1997.9.8.1735"},{"key":"67","doi-asserted-by":"publisher","unstructured":"K. Cho, B. van Merri\u00ebnboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio, ``Learning phrase representations using RNN encoder\u2013decoder for statistical machine translation,'' in Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), edited by A. Moschitti, B. Pang, and W. Daelemans (Association for Computational Linguistics, Doha, 2014) pp. 1724\u20131734.","DOI":"10.3115\/v1\/D14-1179"},{"key":"68","unstructured":"A. Mokhtari, A. Ozdaglar, and A. Jadbabaie, ``Efficient nonconvex empirical risk minimization via adaptive sample size methods,'' in Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 89, edited by K. Chaudhuri and M. Sugiyama (PMLR, Naha, Japan, 2019) pp. 2485\u20132494."},{"key":"69","doi-asserted-by":"publisher","unstructured":"S. Mei, Y. Bai, and A. Montanari, ``The landscape of empirical risk for nonconvex losses,'' Ann. Stat. 46, 2747 (2018).","DOI":"10.1214\/17-AOS1637"},{"key":"70","doi-asserted-by":"publisher","unstructured":"J. Yang, W. Hu, and C. J. Li, ``On the fast convergence of random perturbations of the gradient flow,'' Asymptot. Anal. 122, 371 (2021).","DOI":"10.3233\/ASY-201622"},{"key":"71","unstructured":"R. Dixit, M. Gurbuzbalaban, and W. U. Bajwa, ``Accelerated gradient methods for nonconvex optimization: Escape trajectories from strict saddle points and convergence to local minima,'' (2023), arXiv:2307.07030 [math.OC]."},{"key":"72","doi-asserted-by":"publisher","unstructured":"S. V. Kurochkin, ``Neural network with smooth activation functions and without bottlenecks is almost surely a Morse function,'' Comput. Math. and Math. Phys 61, 1162 (2021).","DOI":"10.1134\/S0965542521070101"},{"key":"73","doi-asserted-by":"publisher","unstructured":"N. Liu, J. Thompson, C. Weedbrook, S. Lloyd, V. Vedral, M. Gu, and K. Modi, ``Power of one qumode for quantum computation,'' Phys. Rev. A 93, 052304 (2016).","DOI":"10.1103\/PhysRevA.93.052304"},{"key":"74","doi-asserted-by":"publisher","unstructured":"D. Gottesman, A. Kitaev, and J. Preskill, ``Encoding a qubit in an oscillator,'' Phys. Rev. A 64, 012310 (2001).","DOI":"10.1103\/PhysRevA.64.012310"},{"key":"75","doi-asserted-by":"publisher","unstructured":"M. A. Nielsen and I. L. Chuang, ``The quantum Fourier transform and its applications,'' in Quantum Computation and Quantum Information: 10th Anniversary Edition (Cambridge University Press, Cambridge, UK, 2010) pp. 216\u2013247.","DOI":"10.1017\/CBO9780511976667.009"},{"key":"76","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, A. Montanaro, and D. 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":"77","doi-asserted-by":"publisher","unstructured":"N. D. Mermin, ``Simple unified form for the major no-hidden-variables theorems,'' Phys. Rev. Lett. 65, 3373 (1990).","DOI":"10.1103\/PhysRevLett.65.3373"},{"key":"78","doi-asserted-by":"publisher","unstructured":"D. Gottesman and I. L. Chuang, ``Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations,'' Nature 402, 390 (1999).","DOI":"10.1038\/46503"},{"key":"79","doi-asserted-by":"publisher","unstructured":"P. J. Rabier, ``Ehresmann fibrations and Palais-Smale conditions for morphisms of Finsler manifolds,'' Ann. Math. 146, 647 (1997).","DOI":"10.2307\/2952457"},{"key":"80","doi-asserted-by":"publisher","unstructured":"L. Isenhower, M. Saffman, and K. M\u00f8lmer, ``Multibit $\\operatorname{C}_k\\operatorname{NOT}$ quantum gates via Rydberg blockade,'' Quantum. Inf. Process. 10, 755 (2011).","DOI":"10.1007\/s11128-011-0292-4"},{"key":"81","doi-asserted-by":"publisher","unstructured":"D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, et al., ``Logical quantum processor based on reconfigurable atom arrays,'' Nature , 1 (2023).","DOI":"10.1038\/s41586-023-06927-3"},{"key":"82","doi-asserted-by":"publisher","unstructured":"A. J. Kerman, ``Quantum information processing using quasiclassical electromagnetic interactions between qubits and electrical resonators,'' New J. Phys. 15, 123011 (2013).","DOI":"10.1088\/1367-2630\/15\/12\/123011"},{"key":"83","doi-asserted-by":"publisher","unstructured":"A. Blais, A. L. Grimsmo, S. M. Girvin, and A. Wallraff, ``Circuit quantum electrodynamics,'' Rev. Mod. Phys. 93, 025005 (2021).","DOI":"10.1103\/RevModPhys.93.025005"},{"key":"84","doi-asserted-by":"publisher","unstructured":"M. Leifer, ``Is the quantum state real? an extended review of $\\psi$-ontology theorems,'' Quanta 3, 67 (2014).","DOI":"10.12743\/quanta.v3i1.22"},{"key":"85","doi-asserted-by":"publisher","unstructured":"S. Bravyi, D. Gosset, R. Koenig, and M. Tomamichel, ``Quantum advantage with noisy shallow circuits,'' Nat. Phys. 16, 1040 (2020).","DOI":"10.1038\/s41567-020-0948-z"},{"key":"86","unstructured":"L. Caha, X. Coiteux-Roy, and R. Koenig, ``A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits,'' (2023), arXiv:2312.09209 [quant-ph]."},{"key":"87","doi-asserted-by":"crossref","unstructured":"M. H. Teo, W. Yang, J. Sud, T. Tomesh, F. T. Chong, and E. R. Anschuetz, ``k-contextuality as a heuristic for memory separations in learning,'' (2025), arXiv:2507.11604 [quant-ph].","DOI":"10.1109\/QCE65121.2025.00260"},{"key":"88","unstructured":"T. Brown et al., ``Language models are few-shot learners,'' in Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, edited by H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (Curran Associates, Inc., Red Hook, NY, USA, 2020) pp. 1877\u20131901."},{"key":"89","unstructured":"OpenAI, ``GPT-4 technical report,'' (2023), arXiv:2303.08774 [cs.CL]."},{"key":"90","doi-asserted-by":"publisher","unstructured":"K. Wan, S. Choi, I. H. Kim, N. Shutty, and P. Hayden, ``Fault-tolerant qubit from a constant number of components,'' PRX Quantum 2, 040345 (2021).","DOI":"10.1103\/PRXQuantum.2.040345"},{"key":"91","unstructured":"M. Srikumar, S. D. Bartlett, and A. Karanjai, ``How contextuality and antidistinguishability are related,'' (2024), arXiv:2411.09919 [quant-ph]."},{"key":"92","doi-asserted-by":"publisher","unstructured":"A. Mari and J. Eisert, ``Positive Wigner functions render classical simulation of quantum computation efficient,'' Phys. Rev. Lett. 109, 230503 (2012).","DOI":"10.1103\/PhysRevLett.109.230503"},{"key":"93","unstructured":"I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, ``Generative adversarial nets,'' in Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2, NIPS'14, edited by Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger (Curran Associates, Inc., Red Hook, NY, USA, 2014) pp. 2672\u20132680."},{"key":"94","unstructured":"B. Shi, W. J. Su, and M. I. Jordan, ``On learning rates and Schr\u00f6dinger operators,'' (2020), arXiv:2004.06977 [cs.LG]."},{"key":"95","unstructured":"R. Duan, H. Wu, and R. Zhou, ``Faster matrix multiplication via asymmetric hashing,'' (2022), arXiv:2210.10173 [cs.DS]."},{"key":"96","doi-asserted-by":"publisher","unstructured":"V. Strassen, ``Gaussian elimination is not optimal,'' Numer. Math. 13, 354 (1969).","DOI":"10.1007\/BF02165411"},{"key":"97","doi-asserted-by":"publisher","unstructured":"S. Aaronson and D. Gottesman, ``Improved simulation of stabilizer circuits,'' Phys. Rev. A 70, 052328 (2004).","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"98","doi-asserted-by":"publisher","unstructured":"C. Calcluth, A. Ferraro, and G. Ferrini, ``Efficient simulation of Gottesman-Kitaev-Preskill states with Gaussian circuits,'' (2022), arXiv:2203.11182 [quant-ph].","DOI":"10.22331\/q-2022-12-01-867"},{"key":"99","doi-asserted-by":"publisher","unstructured":"M. Larocca, P. Czarnik, K. Sharma, G. Muraleedharan, P. J. Coles, and M. Cerezo, ``Diagnosing barren plateaus with tools from quantum optimal control,'' Quantum 6, 824 (2022).","DOI":"10.22331\/q-2022-09-29-824"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-01-20-1976\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T11:53:30Z","timestamp":1768910010000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-01-20-1976\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,20]]},"references-count":100,"URL":"https:\/\/doi.org\/10.22331\/q-2026-01-20-1976","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,20]]},"article-number":"1976"}}