On quantum learning algorithms for noisy linear problems
- URL: http://arxiv.org/abs/2404.03932v1
- Date: Fri, 5 Apr 2024 07:35:06 GMT
- Title: On quantum learning algorithms for noisy linear problems
- Authors: Minkyu Kim, Panjin Kim,
- Abstract summary: 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.
- Score: 0.6430989240829326
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Quantum algorithms have shown successful results in solving noisy linear problems with quantum samples in which cryptographic hard problems are relevant. In this paper the previous results are investigated in detail, leading to new quantum and classical algorithms under the same assumptions as in the earlier works. To be specific, we present a polynomial-time quantum algorithm for solving the ring learning with errors problem with quantum samples which was deemed to be infeasible in [12], as well as polynomial-time classical algorithms that are more efficient than the corresponding quantum algorithms in solving the short integer solution problem with quantum samples and the learning with errors problem with size-reduced quantum samples.
Related papers
- Lower bounds for quantum-inspired classical algorithms via communication complexity [0.5461938536945723]
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.
arXiv Detail & Related papers (2024-02-24T02:15:00Z) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation.
The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large.
We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
arXiv Detail & Related papers (2023-11-16T09:19:01Z) - 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 Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - 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) - Error Analysis of the Variational Quantum Eigensolver Algorithm [0.18188255328029254]
We study variational quantum eigensolver (VQE) and its individual quantum subroutines.
We show through explicit simulation that the VQE algorithm effectively collapses already when single errors occur during a quantum processing call.
arXiv Detail & Related papers (2023-01-18T02:02:30Z) - 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-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) - An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem.
The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
arXiv Detail & Related papers (2020-05-06T14:18:44Z)
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.