Quantum speedup of leverage score sampling and its application
- URL: http://arxiv.org/abs/2301.06107v2
- Date: Sat, 16 Sep 2023 12:24:51 GMT
- Title: Quantum speedup of leverage score sampling and its application
- Authors: Changpeng Shao
- Abstract summary: In this paper, we propose a quantum algorithm to accelerate the computation of leverage scores.
As an application, we propose a new quantum algorithm for rigid regression problems with vector solution outputs.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Leverage score sampling is crucial to the design of randomized algorithms for
large-scale matrix problems, while the computation of leverage scores is a
bottleneck of many applications. In this paper, we propose a quantum algorithm
to accelerate this useful method. The speedup is at least quadratic and could
be exponential for well-conditioned matrices. We also prove some quantum lower
bounds, which suggest that our quantum algorithm is close to optimal. As an
application, we propose a new quantum algorithm for rigid regression problems
with vector solution outputs. It achieves polynomial speedups over the best
classical algorithm known. In this process, we give an improved randomized
algorithm for rigid regression.
Related papers
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
We propose a quantum algorithm inspired by the classical multi-row iteration method.
Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
arXiv Detail & Related papers (2024-09-06T03:32:02Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - Solving the semidefinite relaxation of QUBOs in matrix multiplication
time, and faster with a quantum computer [0.20999222360659603]
We show that some quantum SDO solvers provide speedups in the low-precision regime.
We exploit this fact to exponentially improve the dependence of their algorithm on precision.
A quantum implementation of our algorithm exhibits a worst case running time of $mathcalO left(ns + n1.5 cdot textpolylog left(n, | C |_F, frac1epsilon right)$.
arXiv Detail & Related papers (2023-01-10T23:12:05Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Quantum Algorithm For Estimating Eigenvalue [0.0]
We provide a quantum algorithm for estimating the largest eigenvalue in magnitude of a given Hermitian matrix.
Our quantum procedure can also yield exponential speedup compared to classical algorithms that solve the same problem.
arXiv Detail & Related papers (2022-11-11T13:02:07Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Quantum Levenberg--Marquardt Algorithm for optimization in Bundle
Adjustment [0.0]
We implement a quantum algorithm for solving the linear system of normal equations that calculates the optimization step in Levenberg--Marquardt.
The proposed quantum algorithm dramatically reduces the complexity of this operation with respect to the number of points.
arXiv Detail & Related papers (2022-03-04T13:38:21Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - An optimal quantum sampling regression algorithm for variational
eigensolving in the low qubit number regime [0.0]
We introduce Quantum Sampling Regression (QSR), an alternative hybrid quantum-classical algorithm.
We analyze some of its use cases based on time complexity in the low qubit number regime.
We demonstrate the efficacy of our algorithm for a benchmark problem.
arXiv Detail & Related papers (2020-12-04T00:01:15Z) - 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) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)
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.