Quantum Regularized Least Squares

• URL: http://arxiv.org/abs/2206.13143v3
• Date: Thu, 20 Apr 2023 16:12:20 GMT
• Title: Quantum Regularized Least Squares
• Authors: Shantanav Chakraborty, Aditya Morolia, Anurudh Peduri
• Abstract summary: In most real-world scenarios, linear regression problems are often ill-posed or the underlying model suffers from overfitting. This is often dealt with by adding extra constraints, known as regularization. We use the frameworks of block-encoding and quantum singular value transformation to design the first quantum algorithms for quantum least squares.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from overfitting, leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general $\ell_2$-regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result. To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.

Related papers

• Double-Logarithmic Depth Block-Encodings of Simple Finite Difference Method's Matrices [0.0]
  Solving differential equations is one of the most computationally expensive problems in classical computing. Despite recent progress made in the field of quantum computing and quantum algorithms, its end-to-end application towards practical realization still remains unattainable.
  arXiv  Detail & Related papers  (2024-10-07T17:44:30Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Explainable quantum regression algorithm with encoded data structure [0.0]
  In this paper, we construct the first interpretable quantum regression algorithm.<n>The encoded data structure reduces the time complexity of computing the regression map.<n>We envision potential quantum utilities with multi-qubit gates implemented in neutral cold atoms and ions.
  arXiv  Detail & Related papers  (2023-07-07T00:30:16Z)
• Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms [0.0]
  We show how many techniques from randomized linear algebra can be adapted to work under this weaker assumption. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms.
  arXiv  Detail & Related papers  (2023-04-11T02:09:13Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Improved resource-tunable near-term quantum algorithms for transition probabilities, with applications in physics and variational quantum linear algebra [1.7404865362620803]
  We present three related algorithms for calculating transition probabilities. First, we extend a previously published short-depth algorithm, allowing for the two input states to be non-orthogonal. Second, we derive a higher-depth algorithm based on Trotterization and Richardson extrapolation that requires fewer circuit evaluations. Third, we introduce a tunable algorithm that allows for trading off circuit depth and measurement complexity.
  arXiv  Detail & Related papers  (2022-06-28T18:00:05Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  We propose a general framework termed as permutation filters, which includes the existing permutation-based methods as special cases. We show that the proposed filter design algorithm always converges to the global optimum, and that the optimal filters can provide substantial improvements over the existing permutation-based methods.
  arXiv  Detail & Related papers  (2021-07-03T16:07:30Z)
• 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)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning [7.356328937024184]
  We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices. Motivated by quantum linear algebra algorithms and the quantum singular value transformation framework, we develop classical algorithms for SVT that run in time independent of input dimension. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups.
  arXiv  Detail & Related papers  (2019-10-14T14:04:30Z)

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.