Related papers: Lower bounds for quantum-inspired classical algorithms via communication complexity

Lower bounds for quantum-inspired classical algorithms via communication complexity

URL: http://arxiv.org/abs/2402.15686v2
Date: Thu, 9 May 2024 09:48:35 GMT
Title: Lower bounds for quantum-inspired classical algorithms via communication complexity
Authors: Nikhil S. Mande, Changpeng Shao,
Abstract summary: We focus on lower bounds for solving linear regressions, supervised clustering, principal component analysis, recommendation systems, and Hamiltonian simulations. We prove a quadratic lower bound in terms of the Frobenius norm of the underlying matrix. As quantum algorithms are linear in the Frobenius norm for those problems, our results mean that the quantum-classical separation is at least quadratic.
Score: 0.5461938536945723
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Quantum-inspired classical algorithms provide us with a new way to understand the computational power of quantum computers for practically-relevant problems, especially in machine learning. In the past several years, numerous efficient algorithms for various tasks have been found, while an analysis of lower bounds is still missing. Using communication complexity, in this work we propose the first method to study lower bounds for these tasks. We mainly focus on lower bounds for solving linear regressions, supervised clustering, principal component analysis, recommendation systems, and Hamiltonian simulations. For those problems, we prove a quadratic lower bound in terms of the Frobenius norm of the underlying matrix. As quantum algorithms are linear in the Frobenius norm for those problems, our results mean that the quantum-classical separation is at least quadratic. As a generalisation, we extend our method to study lower bounds analysis of quantum query algorithms for matrix-related problems using quantum communication complexity. Some applications are given.

Related papers

An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning [14.955338558971787]
A provable exponential quantum speedup has been a central research goal since the seminal HHL quantum algorithm for solving linear systems. We present the first such provable exponential separation between quantum and quantum-inspired classical algorithms.
arXiv Detail & Related papers (2024-11-04T13:49:26Z)
On quantum learning algorithms for noisy linear problems [0.6430989240829326]
Quantum algorithms have shown successful results in solving noisy linear problems with quantum samples. New quantum and classical algorithms are presented under the same assumptions as in the earlier works.
arXiv Detail & Related papers (2024-04-05T07:35:06Z)
On the quantum time complexity of divide and conquer [42.7410400783548]
We study the time complexity of quantum divide and conquer algorithms for classical problems. We apply these theorems to an array of problems involving strings, integers, and geometric objects.
arXiv Detail & Related papers (2023-11-28T01:06:03Z)
Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z)
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 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)
Quantum communication complexity of linear regression [0.05076419064097732]
We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
arXiv Detail & Related papers (2022-10-04T13:27:01Z)
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-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)
Quantum Geometric Machine Learning for Quantum Circuits and Control [78.50747042819503]
We review and extend the application of deep learning to quantum geometric control problems. We demonstrate enhancements in time-optimal control in the context of quantum circuit synthesis problems. Our results are of interest to researchers in quantum control and quantum information theory seeking to combine machine learning and geometric techniques for time-optimal control problems.
arXiv Detail & Related papers (2020-06-19T19:12:14Z)

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