Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
- URL: http://arxiv.org/abs/2011.04125v7
- Date: Tue, 28 Jun 2022 18:10:38 GMT
- Title: Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
- Authors: Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin, David
P. Woodruff
- Abstract summary: 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.
- Score: 53.46106569419296
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We create classical (non-quantum) dynamic data structures supporting queries
for recommender systems and least-squares regression that are comparable to
their quantum analogues. De-quantizing such algorithms has received a flurry of
attention in recent years; we obtain sharper bounds for these problems. More
significantly, we achieve these improvements by arguing that the previous
quantum-inspired algorithms for these problems are doing leverage or
ridge-leverage score sampling in disguise; these are powerful and standard
techniques in randomized numerical linear algebra. With this recognition, we
are able to employ the large body of work in numerical linear algebra to obtain
algorithms for these problems that are simpler or faster (or both) than
existing approaches. Our experiments demonstrate that the proposed data
structures also work well on real-world datasets.
Related papers
- 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) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - 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 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) - A streamlined quantum algorithm for topological data analysis with
exponentially fewer qubits [5.478764356647437]
We present an improved quantum algorithm for computing persistent Betti numbers.
We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
arXiv Detail & Related papers (2022-09-26T17:56:11Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings.
We exploit a warm-start strategy to amortize the estimation of the exact gradient.
By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
arXiv Detail & Related papers (2021-11-29T15:10:09Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure.
We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
arXiv Detail & Related papers (2021-06-09T08:05:36Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - Quantum-Inspired Classical Algorithm for Principal Component Regression [1.9105479266011323]
We develop an algorithm for principal component regression that runs in time polylogarithmic to the number of data points.
This exponential speed up allows for potential applications in much larger data sets.
arXiv Detail & Related papers (2020-10-16T20:50:48Z) - Towards quantum advantage via topological data analysis [0.0]
We study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi.
We provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis.
arXiv Detail & Related papers (2020-05-06T06:31:24Z)
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.