Potential and limitations of random Fourier features for dequantizing quantum machine learning

Ryan Sweke; Erik Recio-Armengol; Sofiene Jerbi; Elies Gil-Fuster; Bryce Fuller; Jens Eisert; Johannes Jakob Meyer

doi:10.22331/q-2025-02-20-1640

Potential and limitations of random Fourier features for dequantizing quantum machine learning

Ryan Sweke¹, Erik Recio-Armengol^2,3, Sofiene Jerbi⁴, Elies Gil-Fuster^4,5, Bryce Fuller⁷, Jens Eisert^4,5,6, and Johannes Jakob Meyer⁴

¹IBM Quantum, Almaden Research Center, San Jose, CA, USA
²ICFO-Institut de Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels, Spain
³Eurecat, Centre Tecnologic de Catalunya, Multimedia Technologies, Barcelona, Spain
⁴Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Berlin, Germany
⁵Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany
⁶Helmholtz-Zentrum Berlin für Materialien und Energie, 14109 Berlin, Germany
⁷IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598

Published:	2025-02-20, volume 9, page 1640
Editor:	Marco Cerezo
Eprint:	arXiv:2309.11647v4
Doi:	https://doi.org/10.22331/q-2025-02-20-1640
Citation:	Quantum 9, 1640 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Updated after initial publication: This publication was updated to version v4 after the initial publication. The authors left the following comment on the arXiv:

44 pages (33+11). 6 Figures, with many clarifying figures added to this version from original version. Comments and feedback welcome. Now accepted in Quantum - this is the final version

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} (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} (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.

Featured image: An illustration of the question which motivates this work.

Popular summary

There is currently a huge effort underway to understand both the potential and limitations of quantum algorithms for machine learning tasks. In particular, a lot of focus has been put on variational quantum algorithms for machine learning, in which a parameterized quantum circuit is used as a model class, which is optimized over via a classical optimisation algorithm. One approach to understanding the limitations of such algorithms, is to ask when they can be dequantized. More specifically:

When does there exist an efficient classical algorithm, which can be guaranteed to perform just as well as the quantum algorithm?

In this work, we analyse the potential and limitations of random Fourier features as a tool for dequantizing variational quantum machine learning algorithms, based on the optimization of parametrised quantum circuits, for regression problems. The main contribution of the work is to provide a set of necessary and sufficient conditions for efficient dequantization, in terms of properties of the regression problem, the parameterized quantum circuit, and the choice of parameters for RFF. The hope is that these conditions can be used to better identify potential meaningful applications of variational QML, and aid in the design of parameterized quantum circuit models for these applications.

► BibTeX data

@article{Sweke2025potential,
  doi = {10.22331/q-2025-02-20-1640},
  url = {https://doi.org/10.22331/q-2025-02-20-1640},
  title = {Potential and limitations of random {F}ourier features for dequantizing quantum machine learning},
  author = {Sweke, Ryan and Recio-Armengol, Erik and Jerbi, Sofiene and Gil-Fuster, Elies and Fuller, Bryce and Eisert, Jens and Meyer, Johannes Jakob},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1640},
  month = feb,
  year = {2025}
}

► References

[1] Eric R. Anschuetz, Andreas Bauer, Bobak T. Kiani, and Seth Lloyd, ``Efficient classical algorithms for simulating symmetric quantum systems'' Quantum 7, 1189 (2023).
https://doi.org/10.22331/q-2023-11-28-1189

[2] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini, ``Parameterized quantum circuits as machine learning models'' Quantum Science and Technology 4, 043001 (2019).

[3] 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–644 (2021).

[4] 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).
https://doi.org/10.22331/q-2021-11-17-582

[5] 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–5412 (2016).
https://doi.org/10.1109/CVPR.2016.583

[6] Enrico Fontana, Ivan Rungger, Ross Duncan, and Cristina Cîrstoiu, ``Spectral analysis for noise diagnostics and filter-based digital error mitigation'' (2022).
https://doi.org/10.48550/arXiv.2206.08811
arXiv:2206.08811

[7] Enrico Fontana, Manuel S. Rudolph, Ross Duncan, Ivan Rungger, and Cristina Cîrstoiu, ``Classical simulations of noisy variational quantum circuits'' (2023).
https://doi.org/10.48550/arXiv.2306.05400
arXiv:2306.05400

[8] Andrew J. Ferrisand Guifre Vidal ``Perfect sampling with unitary tensor networks'' Phys. Rev. B 85, 165146 (2012).
https://doi.org/10.1103/PhysRevB.85.165146

[9] Oded Goldreich ``Introduction to property testing'' Cambridge University Press (2017).
https://doi.org/10.1017/9781108135252

[10] 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).
https://doi.org/10.48550/arXiv.1907.03741

[11] Francisco Javier Gil Vidaland Dirk Oliver Theis ``Input redundancy for parameterized quantum circuits'' Frontiers in Physics 8, 297 (2020).
https://doi.org/10.3389/fphy.2020.00297

[12] Sofiene Jerbi, Lukas J. Fiderer, Hendrik Poulsen Nautrup, Jonas M. Kübler, Hans J. Briegel, and Vedran Dunjko, ``Quantum machine learning beyond kernel methods'' Nature Communications 14, 517 (2023).
https://doi.org/10.1038/s41467-023-36159-y

[13] Sofiene Jerbi, Casper Gyurik, Simon C. Marshall, Riccardo Molteni, and Vedran Dunjko, ``Shadows of quantum machine learning'' Nature Communications 15 (2024).
https://doi.org/10.1038/s41467-024-49877-8

[14] Behnoush Khavariand Guillaume Rabusseau ``Lower and Upper Bounds on the VC-Dimension of Tensor Network Models'' (2021).
https://doi.org/10.48550/arXiv.2106.11827
arXiv:2106.11827

[15] Martín Larocca, Frédéric Sauvage, Faris M. Sbahi, Guillaume Verdon, Patrick J. Coles, and M. Cerezo, ``Group-Invariant Quantum Machine Learning'' PRX Quantum 3 (2022).
https://doi.org/10.1103/PRXQuantum.3.030341

[16] Jonas Landman, Slimane Thabet, Constantin Dalyac, Hela Mhiri, and Elham Kashefi, ``Classically approximating variational quantum machine learning with random Fourier features'' (2022).
https://doi.org/10.48550/arXiv.2210.13200
arXiv:2210.13200

[17] 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).
https://doi.org/10.1103/PRXQuantum.4.010328

[18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, ``Foundations of machine learning'' MIT press (2018).

[19] Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito, ``On Learning with Integral Operators'' Journal of Machine Learning Research 11, 905–934 (2010).
http://jmlr.org/papers/v11/rosasco10a.html

[20] Ali Rahimiand Benjamin Recht ``Random Features for Large-Scale Kernel Machines'' Advances in Neural Information Processing Systems 20 (2007).
https://proceedings.neurips.cc/paper_files/paper/2007/file/013a006f03dbc5392effeb8f18fda755-Paper.pdf

[21] Alessandro Rudiand Lorenzo Rosasco ``Generalization Properties of Learning with Random Features'' Advances in Neural Information Processing Systems 30 (2017).
https://proceedings.neurips.cc/paper_files/paper/2017/file/61b1fb3f59e28c67f3925f3c79be81a1-Paper.pdf

[22] Ingo Steinwartand Andreas Christmann ``Support vector machines'' Springer Science & Business Media (2008).
https://doi.org/10.1007/978-0-387-77242-4

[23] Ulrich Schollwöck ``The density-matrix renormalization group in the age of matrix product states'' Annals of Physics 326, 96–192 (2011).
https://doi.org/10.1016/j.aop.2010.09.012

[24] Maria Schuld ``Supervised quantum machine learning models are kernel methods'' (2021).
https://doi.org/10.48550/arXiv.2101.11020
arXiv:2101.11020

[25] Franz J. Schreiber, Jens Eisert, and Johannes Jakob Meyer, ``Classical surrogates for quantum learning models'' Physical Review Letters 131, 100803 (2023).
https://doi.org/10.1103/PhysRevLett.131.100803

[26] Bharath Sriperumbudurand Zoltan Szabo ``Optimal Rates for Random Fourier Features'' Advances in Neural Information Processing Systems 28 (2015).
https://proceedings.neurips.cc/paper_files/paper/2015/file/d14220ee66aeec73c49038385428ec4c-Paper.pdf

[27] Danica J. Sutherlandand Jeff Schneider ``On the Error of Random Fourier Features'' (2015).
https://doi.org/10.48550/arXiv.1506.02785
arXiv:1506.02785

[28] 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).
https://doi.org/10.1103/PhysRevA.103.032430

[29] Seongwook Shin, Yong Siah Teo, and Hyunseok Jeong, ``Dequantizing quantum machine learning models using tensor networks'' Phys. Rev. Res. 6, 023218 (2024).
https://doi.org/10.1103/PhysRevResearch.6.023218

[30] E M Stoudenmireand Steven R White ``Minimally entangled typical thermal state algorithms'' New Journal of Physics 12, 055026 (2010).
https://doi.org/10.1088/1367-2630/12/5/055026

[31] Yuguo Shao, Fuchuan Wei, Song Cheng, and Zhengwei Liu, ``Simulating quantum mean values in noisy variational quantum algorithms: A polynomial-scale approach'' (2023).
https://doi.org/10.48550/arXiv.2306.05804
arXiv:2306.05804

Cited by

[1] Reyhaneh Aghaei Saem, Behrang Tafreshi, Zoë Holmes, and Supanut Thanasilp, "Pitfalls when tackling the exponential concentration of parameterized quantum models", Quantum Science and Technology 11 1, 015049 (2026).

[2] Farai Mazhandu and Mhlambululi Mafu, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 63 (2025) ISBN:979-8-3315-5736-2.

[3] M. Cerezo, Martin Larocca, Diego García-Martín, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, and Zoë Holmes, "Does provable absence of barren plateaus imply classical simulability?", Nature Communications 16 1, 7907 (2025).

[4] Callum Duffy, Marcin Jastrzebski, Stefano Vergani, Leigh H. Whitehead, Ryan Cross, Andrew Blake, Sarah Malik, and John Marshall, "LArTPC hit-based topology classification with quantum machine learning and symmetry considerations", Physical Review D 112 9, 092006 (2025).

[5] Philip Anton Hernicht, Alona Sakhnenko, Corey O’Meara, Giorgio Cortiana, and Jeanette Miriam Lorenz, "Enhancing the scalability of classical surrogates for real-world quantum machine learning applications", Quantum Machine Intelligence 8 2, 83 (2026).

[6] Melvin Strobl, Maja Franz, Eileen Kuehn, Wolfgang Mauerer, and Achim Streit, 2025 IEEE International Conference on Quantum Software (QSW) 238 (2025) ISBN:979-8-3315-6720-0.

[7] Kasidit Srimahajariyapong, Supanut Thanasilp, and Thiparat Chotibut, "Connecting phases of matter to the flatness of the loss landscape in analog variational quantum algorithms", Communications Physics 9 1, 111 (2026).

[8] Marie Kempkes, Aroosa Ijaz, Elies Gil-Fuster, Carlos Bravo-Prieto, Jakob Spiegelberg, Evert van Nieuwenburg, and Vedran Dunjko, "Double Descent in Quantum Kernel Methods", PRX Quantum 7 1, 010312 (2026).

[9] Chen Lijia, Wu Yue, and Wang Chen, 2026 International Conference on Intelligent and Sustainable AI Systems (ICOSAAS) 1 (2026) ISBN:979-8-3315-7974-6.

[10] Slimane Thabet, Léo Monbroussou, Eliott Z. Mamon, and Jonas Landman, "When quantum and classical models disagree: learning beyond minimum norm least square", npj Quantum Information 12 1, 81 (2026).

[11] Seongwook Shin, Ryan Sweke, and Hyunseok Jeong, "Quantum kernels through the lens of entangled tensor kernels", Physical Review Research 8 2, 023181 (2026).

[12] Shawn Jaison S, D. Narmadha, and Naveen Sundar, 2025 4th International Conference on Applied Artificial Intelligence and Computing (ICAAIC) 179 (2025) ISBN:979-8-3315-6587-9.

[13] Yijie Liu, Mengkun Li, Jie Shi, and Qing Kuang, 2025 International Conference on Advanced Computing and Intelligent Robotics Applications (ACIRA) 38 (2025) ISBN:979-8-3315-5742-3.

[14] Wei-You Liao, Yuxuan Du, Xinbiao Wang, Tian-Ci Tian, Yong Luo, Bo Du, Dacheng Tao, and He-Liang Huang, "Demonstration of efficient predictive surrogates for large-scale quantum processors", Nature Communications 17 1, 4731 (2026).

[15] Sacha Lerch, Ricard Puig, Manuel S. Rudolph, Armando Angrisani, Tyson Jones, M. Cerezo, Supanut Thanasilp, and Zoë Holmes, "Efficient Quantum-Enhanced Classical Simulation for Patches of Quantum Landscapes", PRX Quantum 7 2, 020359 (2026).

[16] Hela Mhiri, Leo Monbroussou, Mario Herrero-Gonzalez, Slimane Thabet, Elham Kashefi, and Jonas Landman, "Constrained and Vanishing Expressivity of Quantum Fourier Models", Quantum 9, 1847 (2025).

[17] Yuxuan Du, Yan Zhu, Yuan-Hang Zhang, Min-Hsiu Hsieh, Patrick Rebentrost, Weibo Gao, Yi-Zhuang You, Jens Eisert, Giulio Chiribella, Dacheng Tao, Barry C. Sanders, and Ya-Dong Wu, "Artificial intelligence for representing and characterizing quantum systems", Nature Reviews Physics (2026).

[18] Mierk Schwabe, Lorenzo Pastori, Valentina Sarandrea, and Veronika Eyring, 2025 IEEE International Conference on Quantum Artificial Intelligence (QAI) 73 (2025) ISBN:979-8-3315-6986-0.

[19] Roberto Flórez-Ablan, Marco Roth, and Jan Schnabel, "On the similarity of bandwidth-tuned quantum kernels and classical kernels", Quantum Science and Technology 10 3, 035051 (2025).

[20] Travis L. Scholten, Carl J. Williams, Dustin Moody, Michele Mosca, William Hurley, William J. Zeng, Matthias Troyer, and Jay M. Gambetta, "Assessing the Benefits and Risks of Quantum Computers", arXiv:2401.16317, (2024).

[21] Weijie Xiong, Giorgio Facelli, Mehrad Sahebi, Owen Agnel, Thiparat Chotibut, Supanut Thanasilp, and Zoë Holmes, "On fundamental aspects of quantum extreme learning machines", arXiv:2312.15124, (2023).

[22] Elies Gil-Fuster, Jens Eisert, and Vedran Dunjko, "On the expressivity of embedding quantum kernels", Machine Learning: Science and Technology 5 2, 025003 (2024).

[23] Erik Armengol and Joseph Bowles, "IQPopt: Fast optimization of instantaneous quantum polynomial circuits in JAX", arXiv:2501.04776, (2025).

[24] Diego H. Useche, Sergio Quiroga-Sandoval, Sebastian L. Molina, Vladimir Vargas-Calderón, Juan E. Ardila-García, and Fabio A. González, "Quantum generative classification with mixed states", Quantum Science and Technology 10 4, 045024 (2025).

[25] Elies Gil-Fuster, Jonas R. Naujoks, Grégoire Montavon, Thomas Wiegand, Wojciech Samek, and Jens Eisert, "Opportunities and limitations of explaining quantum machine learning", arXiv:2412.14753, (2024).

[26] Po-Wei Huang and Patrick Rebentrost, "Post-variational quantum neural networks", arXiv:2307.10560, (2023).

[27] Melvin Strobl, M. Emre Sahin, Lucas van der Horst, Eileen Kuehn, Achim Streit, and Ben Jaderberg, "Fourier Fingerprints of Ansatzes in Quantum Machine Learning", arXiv:2508.20868, (2025).

[28] Mehrad Sahebi, Alice Barthe, Yudai Suzuki, Zoë Holmes, and Michele Grossi, "On Dequantization of Supervised Quantum Machine Learning via Random Fourier Features", arXiv:2505.15902, (2025).

[29] Beng Yee Gan, Po-Wei Huang, Elies Gil-Fuster, and Patrick Rebentrost, "Concept learning of parameterized quantum models from limited measurements", arXiv:2408.05116, (2024).

[30] Riddhi S. Gupta, Carolyn E. Wood, Teyl Engstrom, Jason D. Pole, and Sally Shrapnel, "Quantum Machine Learning for Digital Health? A Systematic Review", arXiv:2410.02446, (2024).

[31] Lorenzo Pastori, Arthur Grundner, Veronika Eyring, and Mierk Schwabe, "Quantum Neural Networks for Cloud Cover Parameterizations in Climate Models", arXiv:2502.10131, (2025).

[32] Francesco Scala, Christa Zoufal, Dario Gerace, and Francesco Tacchino, "Towards Practical Quantum Neural Network Diagnostics with Neural Tangent Kernels", arXiv:2503.01966, (2025).

[33] Callum Duffy and Marcin Jastrzebski, "Spectral Bias in Variational Quantum Machine Learning", arXiv:2506.22555, (2025).

[34] Ryan Sweke, Seongwook Shin, and Elies Gil-Fuster, "Kernel-based dequantization of variational QML without Random Fourier Features", arXiv:2503.23931, (2025).

[35] Yudai Suzuki, Rei Sakuma, and Hideaki Kawaguchi, "Light-cone feature selection for quantum machine learning", arXiv:2403.18733, (2024).

[36] Alice Barthe, Mahtab Yaghubi Rad, Michele Grossi, and Vedran Dunjko, "Quantum Advantage in Learning Quantum Dynamics via Fourier coefficient extraction", arXiv:2506.17089, (2025).

[37] Maximilian Wendlinger, Kilian Tscharke, and Pascal Debus, "A Comparative Analysis of Adversarial Robustness for Quantum and Classical Machine Learning Models", arXiv:2404.16154, (2024).

[38] Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi, Jens Eisert, and Maximilian J. Kramer, "Optimal algorithmic complexity of inference in quantum kernel methods", arXiv:2604.15214, (2026).

[39] Melvin Strobl, Maja Franz, Lukas Scheller, Eileen Kuehn, Wolfgang Mauerer, and Achim Streit, "Beyond Gates: Pulse Level Quantum Fourier Models", arXiv:2605.04945, (2026).

[40] Maja Franz, Melvin Strobl, Jonathan Hunz, Lukas Scheller, Lucas van der Horst, Eileen Kuehn, Achim Streit, and Wolfgang Mauerer, "Software Between Quantum and Machine Learning -- And Down to Pulses", arXiv:2605.21286, (2026).

[41] Javier Mancilla and Tomás Tagliani, "The Fourier Wall: Why Public Tabular Datasets Refuse Quantum Advantage, and a Certified Recipe for Where It Lives", arXiv:2607.15815, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 15:16:23) and SAO/NASA ADS (last updated successfully 2026-08-17 15:16:24). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.