Quantum-assisted Gaussian process regression using random Fourier features

• URL: http://arxiv.org/abs/2507.22629v1
• Date: Wed, 30 Jul 2025 12:49:53 GMT
• Title: Quantum-assisted Gaussian process regression using random Fourier features
• Authors: Cristian A. Galvis-Florez, Ahmad Farooq, Simo Särkkä,
• Abstract summary: We introduce a quantum-assisted algorithm for Gaussian process regression based on the random Fourier feature kernel approximation.<n>We achieve a sparse-order computational speedup relative to the classical method.
• Score: 8.271361104403802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probabilistic machine learning models are distinguished by their ability to integrate prior knowledge of noise statistics, smoothness parameters, and training data uncertainty. A common approach involves modeling data with Gaussian processes; however, their computational complexity quickly becomes intractable as the training dataset grows. To address this limitation, we introduce a quantum-assisted algorithm for sparse Gaussian process regression based on the random Fourier feature kernel approximation. We start by encoding the data matrix into a quantum state using a multi-controlled unitary operation, which encodes the classical representation of the random Fourier features matrix used for kernel approximation. We then employ a quantum principal component analysis along with a quantum phase estimation technique to extract the spectral decomposition of the kernel matrix. We apply a conditional rotation operator to the ancillary qubit based on the eigenvalue. We then use Hadamard and swap tests to compute the mean and variance of the posterior Gaussian distribution. We achieve a polynomial-order computational speedup relative to the classical method.

Related papers

• Efficient Gaussian State Preparation in Quantum Circuits [4.930778301847907]
  We propose and analyze a circuit-based approach that starts with single-qubit rotations to form an exponential amplitude profile.<n>We demonstrate that this procedure achieves high fidelity with the target Gaussian state.<n>We conclude that the proposed technique is a promising route to make Gaussian states accessible on noisy quantum hardware.
  arXiv  Detail & Related papers  (2025-07-27T15:15:20Z)
• Assessing Quantum Advantage for Gaussian Process Regression [7.10052009802944]
  We show that several quantum algorithms proposed for Gaussian Process Regression show no exponential speedup.<n>The implications for the quantum runtime algorithms are independent of the complexity of loading classical data on a quantum computer.<n>We supplement our theoretical analysis with numerical verification for popular kernels in machine learning.
  arXiv  Detail & Related papers  (2025-05-28T15:50:56Z)
• Phase estimation with partially randomized time evolution [36.989845156791525]
  Quantum phase estimation combined with Hamiltonian simulation is the most promising algorithmic framework to computing ground state energies on quantum computers.<n>In this paper we use randomization to speed up product formulas, one of the standard approaches to Hamiltonian simulation.<n>We perform a detailed resource estimate for single-ancilla phase estimation using partially randomized product formulas for benchmark systems in quantum chemistry.
  arXiv  Detail & Related papers  (2025-03-07T18:09:32Z)
• Provable Quantum Algorithm Advantage for Gaussian Process Quadrature [8.271361104403802]
  The aim of this paper is to develop novel quantum algorithms for Gaussian process quadrature methods.<n>We propose a quantum low-rank Gaussian process quadrature method based on a Hilbert space approximation of the Gaussian process kernel.<n>We provide a theoretical complexity analysis that shows a quantum computer advantage over classical quadrature methods.
  arXiv  Detail & Related papers  (2025-02-20T11:42:15Z)
• Evaluation of phase shifts for non-relativistic elastic scattering using quantum computers [39.58317527488534]
  This work reports the development of an algorithm that makes it possible to obtain phase shifts for generic non-relativistic elastic scattering processes on a quantum computer.
  arXiv  Detail & Related papers  (2024-07-04T21:11:05Z)
• Quantum-Assisted Hilbert-Space Gaussian Process Regression [0.0]
  We propose a space approximation-based quantum algorithm for Gaussian process regression. Our method consists of a combination of classical basis function expansion with quantum computing techniques.
  arXiv  Detail & Related papers  (2024-02-01T12:13:35Z)
• Randomized semi-quantum matrix processing [0.0]
  We present a hybrid quantum-classical framework for simulating generic matrix functions. The method is based on randomization over the Chebyshev approximation of the target function. We prove advantages on average depths, including quadratic speed-ups on costly parameters.
  arXiv  Detail & Related papers  (2023-07-21T18:00:28Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  We introduce probabilistic unrolling, a method that combines Monte Carlo sampling with iterative linear solvers to circumvent matrix inversions. Our theoretical analyses reveal that unrolling and backpropagation through the iterations of the solver can accelerate gradient estimation for maximum likelihood estimation. In experiments on simulated and real data, we demonstrate that probabilistic unrolling learns latent Gaussian models up to an order of magnitude faster than gradient EM, with minimal losses in model performance.
  arXiv  Detail & Related papers  (2023-06-05T21:08:34Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• A Random Matrix Perspective on Random Tensors [40.89521598604993]
  We study the spectra of random matrices arising from contractions of a given random tensor. Our technique yields a hitherto unknown characterization of the local maximum of the ML problem. Our approach is versatile and can be extended to other models, such as asymmetric, non-Gaussian and higher-order ones.
  arXiv  Detail & Related papers  (2021-08-02T10:42:22Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• Sigma-Delta and Distributed Noise-Shaping Quantization Methods for Random Fourier Features [73.25551965751603]
  We prove that our quantized RFFs allow a high accuracy approximation of the underlying kernels. We show that the quantized RFFs can be further compressed, yielding an excellent trade-off between memory use and accuracy. We empirically show by testing the performance of our methods on several machine learning tasks that our method compares favorably to other state of the art quantization methods in this context.
  arXiv  Detail & Related papers  (2021-06-04T17:24:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.