# Techniques: Classically Approximating Variational Quantum Machine Learning with Random Fourier Features

## What the paper contributes (one paragraph)
The paper gives a classical method that approximates a variational quantum circuit (VQC) machine-learning model from only the description of its architecture, without running the circuit on a quantum computer. It builds on the fact that a VQC with Hamiltonian data encoding is a large Fourier series whose frequency spectrum is fixed by the eigenvalues of the encoding gates, and that the associated kernel is shift invariant. It then adapts Random Fourier Features (RFF): sample a small number of frequencies from that spectrum, form a low-dimensional kernel, and fit a classical linear ridge regression. Three sampling strategies are given (distinct, tree, and grid), the last covering encoding Hamiltonians that are hard to diagonalise. The authors prove sample-complexity bounds showing the number of samples grows only linearly in input dimension and logarithmically in the spectrum size, and confirm on artificial and real datasets that the classical model matches or beats the VQC.

## Techniques offered
- **Random Fourier Features classical approximation of VQC quantum models** - reproduces a Hamiltonian-encoding VQC's learned function classically by sampling a few frequencies from its spectrum to build a low-dimensional shift-invariant kernel and fitting linear ridge regression, supplying a dequantised surrogate that needs only the circuit description.
  - guarantee: statistical approximation bound, with high probability the surrogate and the VQC agree to within a chosen error for a sample count scaling linearly in input dimension and logarithmically in spectrum size (Theorems on Pauli and grid sampling)
  - quote: "We provide general theoretical bounds for classically approximating models built from exponentially large quantum feature space by sampling a few frequencies to build an equivalent low dimensional kernel, and we show experimentally that this approximation is efficient for several encoding strategies."
- **Tree and grid frequency sampling for non-enumerable or non-diagonalisable spectra** - samples spectrum paths through the eigenvalue tree to avoid enumerating an exponentially large spectrum and to weight redundant frequencies, or samples a regular frequency grid up to a guessed maximum when encoding Hamiltonians cannot be diagonalised, extending the approximation to VQCs where the exact spectrum is inaccessible.
  - guarantee: grid-sampling error is bounded by the grid step, giving a controllable bias-variance trade-off, with a sample count of order one over epsilon squared times log of one over the step
  - quote: "Even in this case, we propose a method to approximate the VQC. If the frequencies are unknown, but one can guess an upper bound or their maximum value, we propose the following strategy: We create a grid of frequencies regularly disposed between zero and the upper bound $\omega_{max}$, on each dimension."

## Where it could apply
- Target primitive(s): variational quantum circuits for supervised learning, quantum kernel methods, quantum feature maps with Hamiltonian/Pauli data encoding
- Target application group(s): quantum_ml, platforms_tooling

## Caveats
Nothing is supplied to hardware execution: this is a classical dequantisation tool that bounds and often removes a claimed quantum advantage rather than improving a quantum result. The sample-complexity theorems carry unfavourable constant factors (order one over epsilon squared and one over lambda to the fourth) that the authors state cannot be reached with current resources, so the bounds describe asymptotic scaling rather than practical sample counts. Validity rests on encoding gates of the form exp(-x_i H); alternative encodings such as exp(-arcsin(x_i) H) or simultaneous-component encodings move the model off the shift-invariant Fourier basis and are left open. The method targets agreement on a given dataset, so a low sample count can reflect a VQC fitting an uninformative dataset rather than genuine approximation power.