On Dequantization of Supervised Quantum Machine Learning via Random Fourier Features

• RFF approximates shift-invariant kernels by sampling a feature map from the target kernel’s Fourier transform, and those features can support classical learning tasks.Source: §I · p. 1
• Earlier RFF dequantization work focused on QNN regression, leaving quantum kernel methods and SVM classification unexplored.Source: §I · p. 1
• The work extends RFF dequantization to quantum kernel regression, QSVMs, and QNNs trained with SVM loss.Source: §I · p. 1
• The authors adapt RFF to non-shift-invariant kernels and give sufficient conditions for RFF to reach true risk comparable to quantum models.Source: §I · p. 1
• Experiments compare RFF with QSVM on particle-collision data and report similar performance to a quantum model on a real-world dataset.Source: §I · pp. 1–2

• Bold lowercase letters denote vectors, capital letters denote matrices, and xT and x† denote transpose and conjugate transpose.Source: §II · p. 2
• E[·], inner products, and traces denote expectation, inner product, and trace; norm notation distinguishes l1, l2, and infinity norms, Hilbert-space norms, and Dirac state notation.Source: §II · p. 2

• Supervised learning minimizes true risk, the expected loss under the unknown data distribution, using independently sampled training data and empirical risk.Source: A. Classical Framework · p. 2
• A feature map sends inputs into a Hilbert-space feature space, where data structure can be represented.Source: A. Classical Framework · p. 2
• A kernel measures pairwise similarity and can be expressed as an inner product of feature-map outputs; its associated RKHS norm is defined through such representations.Source: A. Classical Framework · p. 2
• A shift-invariant kernel depends only on the difference between its inputs; Gaussian kernels are an example, while most quantum kernels are described as non-stationary.Source: A. Classical Framework · p. 2

• SVM classification seeks a feature-space hyperplane with maximum margin by minimizing regularized hinge loss.Source: Support Vector Machines · p. 2
• The SVM dual problem uses pairwise feature-map inner products, allowing kernel methods without explicit access to the feature map.Source: Support Vector Machines · p. 2
• Linear ridge regression minimizes mean squared error between labels and trainable feature-map predictions, with regularization also available in the kernel dual problem.Source: Support Vector Machines · p. 2

• Bochner’s theorem represents bounded, normalized, continuous shift-invariant kernels using a probability distribution derived from the kernel’s Fourier transform.Source: Random Fourier Features · p. 2
• RFF samples D independent frequencies from that distribution to generate a random Fourier feature map.Source: Random Fourier Features · p. 2
• With high probability, the feature map approximates the kernel with point-wise error at most ϵ when D is sufficiently large.Source: Random Fourier Features · p. 2

B. Quantum Framework

• Quantum kernel methods evaluate kernels on a quantum computer for data pairs, form a Gram matrix, and then optimize classically.Source: B. Quantum Framework · pp. 2–3
• QNNs encode inputs, apply trainable parameterized gates, and measure an observable; their parameters are optimized for the learning task.Source: B. Quantum Framework · p. 3
• The work assumes Hamiltonian encoding, in which data elements enter circuit layers through gates of the form exp(iH(j)xj).Source: B. Quantum Framework · p. 3
• With this encoding, QNN outputs have a Fourier representation over frequencies determined by the encoding Hamiltonians.Source: B. Quantum Framework · p. 3
• The QNN hypothesis class can be represented by a cosine feature map, making RFF a natural dequantization method; prior work applied it to regression.Source: B. Quantum Framework · p. 3
• RFF-dequantization means polynomial-resource RFF achieves true risk within ϵ of the quantum model’s minimum true risk with high probability.Source: B. Quantum Framework · p. 3

III. RFF DEQUANTIZATION OF QML MODELS

• A Hamiltonian-encoded quantum kernel has a Fourier representation with a positive semidefinite, unit-trace matrix and frequency support set by encoding-Hamiltonian eigenvalues.Source: §III · p. 4
• The proposed non-stationary-kernel RFF algorithm samples frequencies using the eigenvalues and eigenvectors of the kernel’s Fourier transform.Source: §III · p. 4
• For point-wise error ϵ, the stated sample bound scales as Ω(|Ω|2d/ϵ2), while |Ω| grows exponentially with input dimension d.Source: §III · p. 4
• The exponential frequency count makes obtaining the Fourier transform computationally prohibitive even for relatively small systems.Source: §III · p. 4
• Efficiently approximating a quantum kernel is sufficient but not necessary for RFF to match a given quantum model’s performance.Source: §III · p. 4
• The paper presents sufficient dequantization conditions for QNN and quantum-kernel regression, quantum-kernel SVM classification, and QNN-SVM classification.Source: §III · p. 4

A. Dequantization for Regression

• Prior work [8] bounded the true-risk gap between RFF ridge regression and QNN regression and used those bounds to derive sufficient dequantization conditions.Source: A. Dequantization for Regression · p. 4
• The sampling distribution must be easy to sample from, and its maximum probability must scale inversely polynomially with problem size.Source: A. Dequantization for Regression · p. 4
• Alignment requires sampling frequencies in proportion to the magnitudes of the best quantum model’s Fourier coefficients.Source: A. Dequantization for Regression · p. 4
• A distribution close to uniform over an exponentially large frequency set violates the concentration condition.Source: A. Dequantization for Regression · p. 4
• The paper frames alignment as a choice of RFF distribution that minimizes the best quantum model’s RKHS norm.Source: A. Dequantization for Regression · p. 4

2. QK Regression

• RFF dequantization extends to QK regression with non-stationary kernels, including kernels with non-diagonal Fourier transforms.The result gives sufficient conditions for RFF ridge regression to dequantize QK ridge regression.Source: §2 · p. 4
• For QK methods, the figure depicts dequantization when the RFF distribution is both aligned to the target and concentrated; either failure may prevent it.The figure labels the target’s diagonal Fourier distribution qω and contrasts the successful case with unaligned or unconcentrated sampling.Source: Figure 1 · p. 5
• A polynomially bounded RKHS norm of the QK true-risk minimizer is required, excluding overly complex decision functions from the stated guarantee.The paper associates a large norm with potentially poor generalization and says such models may already perform poorly.Source: §2 · p. 5
• The QK-regression conditions share the concentration condition with QNN regression, but use a different alignment condition and add a sampling-independent RKHS-norm condition.The alignment condition generalizes the QNN-regression form to non-stationary kernels; for shift-invariant kernels, it reduces to the QNN-style condition.Source: §2 · p. 5

B. Dequantization for SVM Classification

• The classification analysis covers QSVMs and QNN-SVMs, extending the paper’s dequantization results beyond regression.It studies hinge-loss optimization rather than the mean-square-error loss used for regression.Source: B. Dequantization for SVM Classification · p. 5
• The QSVM solves the dual SVM problem using a quantum-computed kernel matrix, while the QNN-SVM optimizes a primal problem with a trainable QNN decision boundary.Both models are considered for hinge-loss classification.Source: B. Dequantization for SVM Classification · p. 5
• The proposed RFF-based SVM algorithm samples frequencies to construct features and uses sufficient conditions to characterize when it dequantizes these quantum models.The algorithm is inspired by Ref..Source: B. Dequantization for SVM Classification · p. 5

1. Quantum SVM

• The RFF-based SVM algorithm samples frequencies from an input distribution to construct cosine features, then solves the SVM optimization problem using those features.The search radius is an optimization constraint in the analysis and need only be chosen sufficiently large in practice.Source: §1 · p. 5
• The sufficient conditions for QSVM dequantization resemble those for regression, but their first two conditions contain square roots and still capture concentration and alignment.The paper states that the optimal sampling distribution should be proportional to the square root of the diagonal distribution.Source: §1 · p. 6
• The paper relates the concentration measure to 1/2-Rényi entropy and notes that this entropy upper-bounds the distribution tail.A point mass at zero frequency has maximum concentration, while a uniform distribution is anti-concentrated.Source: §1 · p. 6
• The QSVM condition requires the true-risk minimizer’s RKHS norm to be polynomially bounded, corresponding to a feature-space margin that decreases at worst inverse-polynomially with dimension.The paper relates the RKHS norm to the inverse SVM margin.Source: §1 · p. 6

2. QNN-SVM

• For QNN-SVMs, the alignment condition matches Ref. [8], but the bound on the Fourier-coefficient 1-norm is stricter than the RKHS-norm bound used for QSVMs and QK regression.The proposition gives sufficient conditions for RFF to dequantize QNN-SVMs.Source: §2 · p. 6
• The same conditions suffice for QNN regression, and the bounded Fourier-sum condition is broader than Ref. [8]’s concentration condition.Whenever Ref. [8]’s concentration condition holds, the bounded Fourier-sum condition also holds.Source: §2 · p. 6
• The paper locates possible QML advantage in well-performing models with anti-concentrated or otherwise hard-to-sample Fourier spectra; otherwise, these regression and classification tasks are theoretically dequantizable.The stated scope covers QNN and QK regression and classification.Source: §2 · p. 6
• The theoretical conditions may be impractical because the required aligned distribution is not necessarily known, and computing the model’s Fourier transform can require exponential resources.Even when the transform is known, the aligned distribution is not guaranteed to be easy to sample from.Source: §2 · pp. 6–7

IV. NUMERICAL EXPERIMENTS

• The practical comparisons use easy-to-sample distributions rather than an optimal RFF distribution, and compare against quantum models measured with finite shots.The authors note that shot noise can significantly impair quantum-model performance because losses and kernel values may concentrate around data-independent values.Source: §IV · p. 7
• The experiments use simulated proton-proton collisions for two-class SVM classification, with feature dimensions reduced to 16, 32, or 64.The dataset mixes Standard Model and Beyond Standard Model processes; the quantum kernel is inspired by the prior work described in Fig. 8 of Appendix I.Source: §IV · p. 7
• Convolutional sampling follows a Pascal-triangle frequency profile, while truncated-convolutional sampling assigns zero probability to the upper half of frequencies.The convolutional profile is motivated by the frequency distribution of quantum kernels; truncated sampling retains the lower half in proportion to that profile.Source: §IV · p. 7, Figure 4 · p. 7
• Truncated-convolutional sampling performs slightly better than convolutional sampling, while uniform sampling fails on this dataset.Because the full frequency support grows exponentially with dimension, truncation gives low frequencies a higher sampling chance when the dataset consists of low frequencies.Source: §IV · pp. 7–8, Figure 3 · p. 7
• RFF-SVM with truncated sampling can outperform QSVMs at different shot-noise levels, and fewer RFF samples are needed to beat QSVMs with small shot counts.The 5-layer, 16-qubit QSVM with 100 shots also performs better than exact-kernel evaluation, which the authors attribute to shot noise acting like regularization.Source: §IV · p. 8, Figure 5 · p. 8
• The minimum RFF sample count needed to reach estimated risk 0.15 grows polynomially with input dimension on this dataset.The scaling plot uses PCA-reduced 64-dimensional data, 1,000 training points, 200 test points, and averages over 20 runs; its fitted line has regression score 0.89.Source: §IV · p. 8, Figure 6 · p. 8

V. CONCLUSION

• The analysis extends RFF dequantization beyond QNN regression to quantum-kernel methods and SVM classification, giving conditions for classical RFF models to achieve comparable true risks.These conditions are provided in Propositions III.3, III.4, and III.5.Source: §V · p. 8
• Alignment requires the optimal RFF sampling distribution to be determined by the QK Fourier spectrum or QNN optimal decision function and be efficient to find or sample.Concentration requires this distribution to be sufficiently concentrated: a lower bound on its infinity norm for regression and an upper bound on its 1/2-Renyi entropy for QSVM.Source: §V · p. 8
• Finding the full optimal sampling distribution is computationally costly for large circuits, and even efficient access may leave sampling complexity as an obstacle.Obtaining the needed information without a full Fourier transform remains an open question.Source: §V · pp. 8–9
• On compressed high-energy-physics datasets, simple, separable, task-independent RFF distributions can bypass circuit Fourier analysis and outperform QSVM.Although the theoretical comparison is with noiseless quantum models, experiments suggest low shot noise may improve generalization; its interaction with RFF dequantization remains unexplored.Source: §V · p. 9
• Extending the analysis beyond Hamiltonian encoding is identified as a future direction, since this study uses that encoding to express QML models as finite Fourier series.The passage begins to introduce alternative encodings but does not specify them.Source: §V · p. 9

5. Random Fourier Features

• The general RFF approximation cannot be used for non-stationary kernels when F(ω1,ω2) is not guaranteed to be real and non-negative, since it cannot generally define a probability distribution.The passage notes that non-stationary kernels can be written in a form similar to shift-invariant kernels, but this distribution issue remains.Source: §5 · p. 17

Appendix C: Approximation of Quantum Kernels with Random Features

• The proposed RFF method approximates a family of non-stationary discrete-spectrum kernels, with fidelity quantum kernels as the focus.The method expresses the kernel as an expected inner product of feature maps and estimates it using a sample mean.Source: Appendix C · p. 17
• The Cholesky and eigenvalue approaches have different error-bound trade-offs: Cholesky bounds are tighter and more interpretable, while eigenvalue bounds recover the RFF bounds for shift-invariant kernels.The eigenvalue bounds therefore generalize the results of Ref..Source: Appendix C · p. 17

1. Settings & Definitions

• For discrete-spectrum kernels, the Fourier transform matrix F is positive semidefinite and unit-trace, supporting diagonal, eigenvalue, and Cholesky probability distributions.The diagonal distribution is used in the main text’s sufficient conditions.Source: §1 · pp. 17–18

2. Kernel Approximation using Cholesky Decomposition

• The Cholesky method guarantees sup_x,y∈X |s(x,y) − k(x,y)| ≤ ε with fixed probability at a stated feature dimension.The guarantee assumes a discrete-spectrum kernel and a compact input set; the supplied passage does not show the feature-dimension expression.Source: §2 · p. 19
• For fidelity quantum kernels, the η2 upper bound suggests dimensionally hard approximation, but the authors conjecture it is lower for most kernels because they are low pass.The passage notes that high-frequency Fourier coefficients are relatively low for most fidelity quantum kernels.Source: §2 · p. 22

3. Kernel Approximation using Eigendecomposition

• The eigendecomposition bound depends on the kernel’s non-stationarity measure; for shift-invariant kernels, it recovers the bounds in Ref..The section also derives upper bounds on point-wise approximation error for the Cholesky and eigenvalue decompositions.Source: §3 · pp. 23–24
• Alg. 2 has better scaling with D when its feature-product samples are η2-sub-Gaussian and η2 ≤ |Ω/4|.The comparison is between the two derived upper bounds for approximating discrete-spectrum kernels.Source: §3 · p. 24

Appendix D: Alternative Alignment Condition of Ref. [8]

• For Ref. [8], choosing p proportional to |c|, the Fourier spectrum of fQNN, minimizes the RKHS norm and the data-sample requirement for dequantization.The appendix derives this alignment condition as the minimizer of the RKHS norm for the re-weighted kernel.Source: Appendix D · pp. 24–26

4. Numerical Experiment

• Both Alg. 2 and Alg. 3 converge to zero approximation error, with Alg. 2 slightly better, apparently through the prefactor of the exponential decay over D.The experiment uses a 2-qubit, 2-layer kernel and averages over 50 runs; the figure shows the approximation error over random-feature counts.Source: §4 · p. 24, Figure 7 · p. 25

Appendix E: Kernel Ridge Regression and RFF

• For functions in kernel k’s RKHS with norm less than constant C, when frequency samples D exceed a threshold of O(√(m log(√m))), the true-risk gap from minimum risk decays as O(m^-1/2).Source: Appendix E · p. 27
• Lemma E.3 bounds RKHS norms across a diagonal-Fourier shift-invariant kernel and a non-diagonal-Fourier kernel sharing the same frequency support.This connection lets the RFF regression bound be applied when the quantum-kernel risk minimizer lies in the corresponding bounded RKHS class.Source: Appendix E · pp. 27–28
• With a polynomially bounded quantum-kernel risk-minimizer norm and Theorem E.4’s conditions, polynomial m and D in d and ε^-1 suffice for QK regression dequantization.The resulting RFF true-risk gap is at most ε; the proof also assumes the regression-label bound is constant in d.Source: Appendix E · pp. 29–30

Appendix F: Bounds for RFF-SVM (Alg. 1)

• The appendix adapts the kitchen-sink guarantee [9] to RFF-SVM, whose two bounded feature functions accommodate the paired cosine and sine features used by RFF.The authors identify their algorithm as a special case of the kitchen-sink method; later bounds use the QK-SVM risk optimizer’s inclusion in Fp,C to establish dequantization.Source: Appendix F · p. 31
• RFF-SVM with regularized hinge loss and sine/cosine features has a performance guarantee for finite discrete sampling distributions.The proof accounts for regularization by bounding its added empirical-risk term by λC²/(2D).Source: Appendix F · p. 33

1. Proof of Prop. III.4

• RFF-SVM can dequantize QSVM when the comparison constants C1 and C2 scale polynomially, using polynomially many data points and frequency samples for an ε-small risk gap.The sufficient sample requirement is Ω((C1C2)²/ε²) for both data and frequency samples.Source: §1 · pp. 36–37
• The theorem relates the RFF-dequantization–QSVM performance gap to data size m and frequency-sample count D; as D grows, RFF-SVM converges to kernel SVM, and the limiting bound is O(1/√m).Corollary G.3 gives sufficient choices of m and D to achieve precision ε with probability 1−2δ over data and frequency samples.Source: §1 · pp. 35–36

Appendix G: Dequantization of QSVM and QNN-SVM

• An alternative performance comparison requires conditions only on the QSVM true-risk minimizer, making it useful for QNN-SVM, which does not explicitly use a kernel.The appendix presents this alternative bound and a corresponding corollary.Source: §1 · pp. 37–38

1. Proof of Prop. III.4

• For Prop. III.4, choosing the number of frequency samples D and data points m sufficiently large ensures the RFF model’s true risk is within ϵ of the quantum model with probability 1 − 2δ.The proof notes that the result extends to empirical risk minimizers because regularized kernel regression and SVM empirical minimizers lie in the kernel RKHS by the representer theorem.Source: §1 · p. 38

2. Proof of Prop. III.5

• RFF-SVM can dequantize QNN-SVM when C0 scales polynomially with input dimension d and the sampling distribution is aligned with the Fourier coefficients.The proposition also requires a bounded Fourier norm; under these conditions, the data and frequency sample requirements are polynomial in d and ϵ^-1.Source: §2 · pp. 38–39

Appendix H: RFF Generalization Bounds and Sufficient Conditions for the Dequantization of QNN Ridge Regression

• The appendix applies Ref. to linear regression and derives alternative QNN regression dequantization conditions broader than Ref. [8]’s concentration condition.It attributes the broader conditions to Ref. [8] relying on stronger assumptions, which yield tighter sufficient conditions.Source: Appendix H · p. 39

1. Generalization Bounds for RFF Regression

• RFF ridge regression has a generalization guarantee for bounded labels and bounded feature functions, established by combining estimation and approximation error bounds.The proof bounds the estimation error between true and empirical risk and the approximation error relative to the function class Fp,C,ϕ1,ϕ2.Source: §1 · pp. 40–41

a. Proof of Lemma H.2

• Using two feature functions, the RFF class has Rademacher complexity at most 2C/√m; together with Theorem H.3, this proves Lemma H.2.The bound for one feature function is C/√m.Source: a. Proof of Lemma H.2 · p. 41

2. Generalization Gap of QNN Ridge Regression and RFF Regression

• Theorem H.4 bounds the RFF–QNN true-risk gap when the QNN optimizer’s Fourier coefficients satisfy the stated constraints relative to the sampling distribution.The bound applies to the output of Algorithm 7 with D frequency samples, search radius C0, and distribution p̃.Source: §2 · p. 42
• RFF dequantizes QNN regression under sufficient conditions that include sampling frequencies in proportion to the optimal QNN decision function’s Fourier coefficients.The alignment condition sets pω = |cω|/C0.Source: §2 · p. 42
• The proposed concentration condition is weaker than Ref. [8]’s: whenever that earlier condition holds, this one does too, but not conversely.The authors conclude that their sufficient conditions cover a larger class of QNN models.Source: §2 · p. 43

Appendix I: Numerical Experiments with Data from Ref. [28]

• RFF-SVM outperforms QSVM on balanced two-class proton-collision classification; the experiment used 1,000 training and 200 test points.The data are simulated proton-proton collisions, classically reduced with an autoencoder and encoded using the quantum feature map.Source: Appendix I · p. 43

1. Analytical Justification for Application of truncated convolutional sampling

• For smooth functions, Fourier tails decay as |ω|^-k, supporting lower-frequency-prioritized or truncated sampling for datasets originating from such functions.The authors argue that most real-life datasets originate from smooth functions.Source: §1 · pp. 43–44

2. The Effect of the Shot Noise on Generalization of QML

• Under Proposition I.3’s conditions, shot noise makes the stated upper bound tighter for the noisy than the noiseless Gram matrix.The analysis models shot noise as additive Gaussian noise and cautions that the bound is not necessarily tight for every problem; the experiment uses SVM classification, unlike the ridge-regression analysis, and omits inference noise.Source: §2 · pp. 44–46

Appendix J: Relation to Barren Plateaus and Exponential Concentration

• Barren plateaus and RFF dequantization are largely orthogonal for QNNs; for quantum kernels, exponential concentration does not by itself establish dequantizability or its absence.The sufficient conditions do not provide necessary conditions for dequantization.Source: Appendix J · p. 46
• Some concentrated frequency distributions may still be unsuitable for RFF if sampling them is hard; peaked distributions are proposed as a possible example.The authors leave this as an open question.Source: Appendix J · p. 47