{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T03:24:00Z","timestamp":1781321040137,"version":"3.54.1"},"reference-count":31,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T00:00:00Z","timestamp":1740009600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Severo Ochoa","award":["CEX2019-000910-S"],"award-info":[{"award-number":["CEX2019-000910-S"]}]},{"name":"FUNQIP and European Union NextGenerationEU","award":["PRTR-C17.I1"],"award-info":[{"award-number":["PRTR-C17.I1"]}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["PASQuanS2.1, 101113690"],"award-info":[{"award-number":["PASQuanS2.1, 101113690"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Quantum machine learning is arguably one of the most explored applications of near-term quantum devices. Much focus has been put on notions of variational quantum machine learning where parameterized quantum circuits<\/mml:mtext><\/mml:mrow><\/mml:math> (PQCs) are used as learning models. These PQC models have a rich structure which suggests that they might be amenable to efficient dequantization via random Fourier features<\/mml:mtext><\/mml:mrow><\/mml:math> (RFF). In this work, we establish necessary and sufficient conditions under which RFF does indeed provide an efficient dequantization of variational quantum machine learning for regression. We build on these insights to make concrete suggestions for PQC architecture design, and to identify structures which are necessary for a regression problem to admit a potential quantum advantage via PQC based optimization.<\/jats:p>","DOI":"10.22331\/q-2025-02-20-1640","type":"journal-article","created":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T14:39:01Z","timestamp":1740062341000},"page":"1640","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":16,"title":["Potential and limitations of random Fourier features for dequantizing quantum machine learning"],"prefix":"10.22331","volume":"9","author":[{"given":"Ryan","family":"Sweke","sequence":"first","affiliation":[{"name":"IBM Quantum, Almaden Research Center, San Jose, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erik","family":"Recio-Armengol","sequence":"additional","affiliation":[{"name":"ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels, Spain"},{"name":"Eurecat, Centre Tecnologic de Catalunya, Multimedia Technologies, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sofiene","family":"Jerbi","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elies","family":"Gil-Fuster","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Berlin, Germany"},{"name":"Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bryce","family":"Fuller","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Eisert","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Berlin, Germany"},{"name":"Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany"},{"name":"Helmholtz-Zentrum Berlin f\u00fcr Materialien und Energie, 14109 Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johannes Jakob","family":"Meyer","sequence":"additional","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2025,2,20]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Eric R. Anschuetz, Andreas Bauer, Bobak T. Kiani, and Seth Lloyd, ``Efficient classical algorithms for simulating symmetric quantum systems'' Quantum 7, 1189 (2023).","DOI":"10.22331\/q-2023-11-28-1189"},{"key":"1","doi-asserted-by":"crossref","unstructured":"Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini, ``Parameterized quantum circuits as machine learning models'' Quantum Science and Technology 4, 043001 (2019).","DOI":"10.1088\/2058-9565\/ab4eb5"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles, ``Variational quantum algorithms'' Nature Reviews Physics 3, 625\u2013644 (2021).","DOI":"10.1038\/s42254-021-00348-9"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Matthias C. Caro, Elies Gil-Fuster, Johannes Jakob Meyer, Jens Eisert, and Ryan Sweke, ``Encoding-dependent generalization bounds for parametrized quantum circuits'' Quantum 5, 582 (2021).","DOI":"10.22331\/q-2021-11-17-582"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Jen-Hao Rick Chang, Aswin C. Sankaranarayanan, and B. V. K. Vijaya Kumar, ``Random Features for Sparse Signal Classification'' 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 5404\u20135412 (2016).","DOI":"10.1109\/CVPR.2016.583"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Enrico Fontana, Ivan Rungger, Ross Duncan, and Cristina C\u00eerstoiu, ``Spectral analysis for noise diagnostics and filter-based digital error mitigation'' (2022).","DOI":"10.48550\/arXiv.2206.08811"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Enrico Fontana, Manuel S. Rudolph, Ross Duncan, Ivan Rungger, and Cristina C\u00eerstoiu, ``Classical simulations of noisy variational quantum circuits'' (2023).","DOI":"10.48550\/arXiv.2306.05400"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Andrew J. Ferrisand Guifre Vidal ``Perfect sampling with unitary tensor networks'' Phys. Rev. B 85, 165146 (2012).","DOI":"10.1103\/PhysRevB.85.165146"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Oded Goldreich ``Introduction to property testing'' Cambridge University Press (2017).","DOI":"10.1017\/9781108135252"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and Ignacio Cirac, ``Expressive power of tensor-network factorizations for probabilistic modeling'' Advances in Neural Information Processing Systems 32 (2019).","DOI":"10.48550\/arXiv.1907.03741"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Francisco Javier Gil Vidaland Dirk Oliver Theis ``Input redundancy for parameterized quantum circuits'' Frontiers in Physics 8, 297 (2020).","DOI":"10.3389\/fphy.2020.00297"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Sofiene Jerbi, Lukas J. Fiderer, Hendrik Poulsen Nautrup, Jonas M. K\u00fcbler, Hans J. Briegel, and Vedran Dunjko, ``Quantum machine learning beyond kernel methods'' Nature Communications 14, 517 (2023).","DOI":"10.1038\/s41467-023-36159-y"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Sofiene Jerbi, Casper Gyurik, Simon C. Marshall, Riccardo Molteni, and Vedran Dunjko, ``Shadows of quantum machine learning'' Nature Communications 15 (2024).","DOI":"10.1038\/s41467-024-49877-8"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Behnoush Khavariand Guillaume Rabusseau ``Lower and Upper Bounds on the VC-Dimension of Tensor Network Models'' (2021).","DOI":"10.48550\/arXiv.2106.11827"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Mart\u00edn Larocca, Fr\u00e9d\u00e9ric Sauvage, Faris M. Sbahi, Guillaume Verdon, Patrick J. Coles, and M. Cerezo, ``Group-Invariant Quantum Machine Learning'' PRX Quantum 3 (2022).","DOI":"10.1103\/PRXQuantum.3.030341"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Jonas Landman, Slimane Thabet, Constantin Dalyac, Hela Mhiri, and Elham Kashefi, ``Classically approximating variational quantum machine learning with random Fourier features'' (2022).","DOI":"10.48550\/arXiv.2210.13200"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Johannes Jakob Meyer, Marian Mularski, Elies Gil-Fuster, Antonio Anna Mele, Francesco Arzani, Alissa Wilms, and Jens Eisert, ``Exploiting Symmetry in Variational Quantum Machine Learning'' PRX Quantum 4, 010328 (2023).","DOI":"10.1103\/PRXQuantum.4.010328"},{"key":"17","unstructured":"Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, ``Foundations of machine learning'' MIT press (2018)."},{"key":"18","unstructured":"Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito, ``On Learning with Integral Operators'' Journal of Machine Learning Research 11, 905\u2013934 (2010)."},{"key":"19","unstructured":"Ali Rahimiand Benjamin Recht ``Random Features for Large-Scale Kernel Machines'' Advances in Neural Information Processing Systems 20 (2007)."},{"key":"20","unstructured":"Alessandro Rudiand Lorenzo Rosasco ``Generalization Properties of Learning with Random Features'' Advances in Neural Information Processing Systems 30 (2017)."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Ingo Steinwartand Andreas Christmann ``Support vector machines'' Springer Science & Business Media (2008).","DOI":"10.1007\/978-0-387-77242-4"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Ulrich Schollw\u00f6ck ``The density-matrix renormalization group in the age of matrix product states'' Annals of Physics 326, 96\u2013192 (2011).","DOI":"10.1016\/j.aop.2010.09.012"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Maria Schuld ``Supervised quantum machine learning models are kernel methods'' (2021).","DOI":"10.48550\/arXiv.2101.11020"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Franz J. Schreiber, Jens Eisert, and Johannes Jakob Meyer, ``Classical surrogates for quantum learning models'' Physical Review Letters 131, 100803 (2023).","DOI":"10.1103\/PhysRevLett.131.100803"},{"key":"25","unstructured":"Bharath Sriperumbudurand Zoltan Szabo ``Optimal Rates for Random Fourier Features'' Advances in Neural Information Processing Systems 28 (2015)."},{"key":"26","doi-asserted-by":"publisher","unstructured":"Danica J. Sutherlandand Jeff Schneider ``On the Error of Random Fourier Features'' (2015).","DOI":"10.48550\/arXiv.1506.02785"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Maria Schuld, Ryan Sweke, and Johannes Jakob Meyer, ``Effect of data encoding on the expressive power of variational quantum-machine-learning models'' Phys. Rev. A 103, 032430 (2021).","DOI":"10.1103\/PhysRevA.103.032430"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Seongwook Shin, Yong Siah Teo, and Hyunseok Jeong, ``Dequantizing quantum machine learning models using tensor networks'' Phys. Rev. Res. 6, 023218 (2024).","DOI":"10.1103\/PhysRevResearch.6.023218"},{"key":"29","doi-asserted-by":"publisher","unstructured":"E M Stoudenmireand Steven R White ``Minimally entangled typical thermal state algorithms'' New Journal of Physics 12, 055026 (2010).","DOI":"10.1088\/1367-2630\/12\/5\/055026"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Yuguo Shao, Fuchuan Wei, Song Cheng, and Zhengwei Liu, ``Simulating quantum mean values in noisy variational quantum algorithms: A polynomial-scale approach'' (2023).","DOI":"10.48550\/arXiv.2306.05804"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-02-20-1640\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T15:43:50Z","timestamp":1742831030000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-02-20-1640\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,20]]},"references-count":31,"URL":"https:\/\/doi.org\/10.22331\/q-2025-02-20-1640","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,20]]},"article-number":"1640"}}