Accelerating Regression Tasks with Quantum Algorithms

• URL: http://arxiv.org/abs/2509.24757v1
• Date: Mon, 29 Sep 2025 13:22:59 GMT
• Title: Accelerating Regression Tasks with Quantum Algorithms
• Abstract summary: We present a unified quantum framework for accelerating a broad class of regression tasks.<n>This speedup is achieved by extending the recent classical breakthrough of Jambulapati et al.<n>For problems of dimension $n$, sparsity $r n$, and error parameter $epsilon$, our algorithm solves the problem in $widetildeO(rsqrtmn/epsilon + mathrmpoly(n,1/epsilon))$ quantum time.
• Score: 2.37771211295026
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Regression is a cornerstone of statistics and machine learning, with applications spanning science, engineering, and economics. While quantum algorithms for regression have attracted considerable attention, most existing work has focused on linear regression, leaving many more complex yet practically important variants unexplored. In this work, we present a unified quantum framework for accelerating a broad class of regression tasks -- including linear and multiple regression, Lasso, Ridge, Huber, $\ell_p$-, and $\delta_p$-type regressions -- achieving up to a quadratic improvement in the number of samples $m$ over the best classical algorithms. This speedup is achieved by extending the recent classical breakthrough of Jambulapati et al. (STOC'24) using several quantum techniques, including quantum leverage score approximation (Apers &Gribling, 2024) and the preparation of many copies of a quantum state (Hamoudi, 2022). For problems of dimension $n$, sparsity $r < n$, and error parameter $\epsilon$, our algorithm solves the problem in $\widetilde{O}(r\sqrt{mn}/\epsilon + \mathrm{poly}(n,1/\epsilon))$ quantum time, demonstrating both the applicability and the efficiency of quantum computing in accelerating regression tasks.

Related papers

• Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations [0.46664938579243576]
  We prove constant factor bounds for a promising new quantum differential equation solver, the linear combination of Hamiltonian simulation algorithm.<n>Our new formulae improve over previous state of the art by at least two orders of magnitude, where the speedup can be far greater if state preparation has a significant cost.
  arXiv  Detail & Related papers  (2025-06-25T18:50:44Z)
• Quantum simulation of Burgers turbulence: Nonlinear transformation and direct evaluation of statistical quantities [0.0]
  It is still challenging to solve nonlinear equations in fluid dynamics, such as the Burgers equation, using quantum computers.<n>We propose a novel quantum algorithm to solve the Burgers equation.
  arXiv  Detail & Related papers  (2024-12-23T01:17:26Z)
• fastkqr: A Fast Algorithm for Kernel Quantile Regression [6.850636409964172]
  We introduce fastkqr, which significantly advances the computation of quantile regression in reproducing kernel Hilbert spaces.<n>The core of fastkqr is a finite smoothing algorithm that magically produces exact regression quantiles, rather than approximations.<n>In addition, we extend fastkqr to accommodate a flexible kernel quantile regression with a data-driven crossing penalty.
  arXiv  Detail & Related papers  (2024-08-10T00:18:56Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD.<n>Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers.<n>Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
  arXiv  Detail & Related papers  (2024-04-30T23:55:03Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• F-Divergences and Cost Function Locality in Generative Modelling with Quantum Circuits [0.0]
  We consider training a quantum circuit Born machine using $f$-divergences. We introduce two algorithms which demonstrably improve the training of the Born machine. We discuss the long-term implications of quantum devices for computing $f$-divergences.
  arXiv  Detail & Related papers  (2021-10-08T17:04:18Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Linear Regression by Quantum Amplitude Estimation and its Extension to Convex Optimization [0.0]
  We propose a new quantum algorithm for linear regression, which has the complexity of $O(epsilon-1)$ and keeps the logarithmic dependence on the number of data points $N_D$. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have the complexity proportional to $N_D$.
  arXiv  Detail & Related papers  (2021-05-28T00:04:11Z)

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.