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

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.

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

References in corpus (14)

• The density-matrix renormalization group in the age of matrix product states
• Minimally Entangled Typical Thermal State Algorithms
• Quantum machine learning beyond kernel methods
• Exploiting symmetry in variational quantum machine learning
• Supervised quantum machine learning models are kernel methods
• Group-Invariant Quantum Machine Learning
• Shadows of quantum machine learning
• Classical surrogates for quantum learning models
• Efficient classical algorithms for simulating symmetric quantum systems
• Dequantizing quantum machine learning models using tensor networks
• Classically Approximating Variational Quantum Machine Learning with Random Fourier Features
• Classical simulations of noisy variational quantum circuits
• Lower and Upper Bounds on the VC-Dimension of Tensor Network Models
• Spectral analysis for noise diagnostics and filter-based digital error mitigation

Cited by in corpus (11)

• Does provable absence of barren plateaus imply classical simulability?
• Constrained and Vanishing Expressivity of Quantum Fourier Models
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• On the similarity of bandwidth-tuned quantum kernels and classical kernels
• Pitfalls when tackling the exponential concentration of parameterized quantum models
• When Quantum and Classical Models Disagree: Learning Beyond Minimum Norm Least Square
• Artificial intelligence for representing and characterizing quantum systems
• Double descent in quantum kernel methods
• New perspectives on quantum kernels through the lens of entangled tensor kernels
• Quantum Machine Learning for Climate Modelling
• LArTPC hit-based topology classification with quantum machine learning and symmetry