A rigorous and robust quantum speed-up in supervised machine learning
- URL: http://arxiv.org/abs/2010.02174v2
- Date: Mon, 30 Nov 2020 18:39:39 GMT
- Title: A rigorous and robust quantum speed-up in supervised machine learning
- Authors: Yunchao Liu, Srinivasan Arunachalam, Kristan Temme
- Abstract summary: In this paper, we establish a rigorous quantum speed-up for supervised classification using a general-purpose quantum learning algorithm.
Our quantum classifier is a conventional support vector machine that uses a fault-tolerant quantum computer to estimate a kernel function.
- Score: 6.402634424631123
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Over the past few years several quantum machine learning algorithms were
proposed that promise quantum speed-ups over their classical counterparts. Most
of these learning algorithms either assume quantum access to data -- making it
unclear if quantum speed-ups still exist without making these strong
assumptions, or are heuristic in nature with no provable advantage over
classical algorithms. In this paper, we establish a rigorous quantum speed-up
for supervised classification using a general-purpose quantum learning
algorithm that only requires classical access to data. Our quantum classifier
is a conventional support vector machine that uses a fault-tolerant quantum
computer to estimate a kernel function. Data samples are mapped to a quantum
feature space and the kernel entries can be estimated as the transition
amplitude of a quantum circuit. We construct a family of datasets and show that
no classical learner can classify the data inverse-polynomially better than
random guessing, assuming the widely-believed hardness of the discrete
logarithm problem. Meanwhile, the quantum classifier achieves high accuracy and
is robust against additive errors in the kernel entries that arise from finite
sampling statistics.
Related papers
- Towards Entropic Constraints on Quantum Speedups [0.0]
Some quantum algorithms have "quantum speedups": improved time complexity as compared with the best-known classical algorithms for solving the same tasks.
Can we understand what fuels these speedups from an entropic perspective?
Information theory gives us a multitude of metrics we might choose from to measure how fundamentally 'quantum' is the behavior of a quantum computer running an algorithm.
arXiv Detail & Related papers (2024-11-05T19:00:04Z) - The curse of random quantum data [62.24825255497622]
We quantify the performances of quantum machine learning in the landscape of quantum data.
We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits.
Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
arXiv Detail & Related papers (2024-08-19T12:18:07Z) - Quantum Machine Learning: from physics to software engineering [58.720142291102135]
We show how classical machine learning approach can help improve the facilities of quantum computers.
We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
arXiv Detail & Related papers (2023-01-04T23:37:45Z) - 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) - Revisiting dequantization and quantum advantage in learning tasks [3.265773263570237]
We show that classical algorithms with sample and query (SQ) access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs.
Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs.
arXiv Detail & Related papers (2021-12-01T20:05:56Z) - The Inductive Bias of Quantum Kernels [0.0]
We analyze function classes defined via quantum kernels.
We show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements.
arXiv Detail & Related papers (2021-06-07T16:14:32Z) - Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise.
Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
arXiv Detail & Related papers (2021-03-31T02:41:36Z) - Quantum Discriminator for Binary Classification [0.0]
We propose a novel quantum machine learning model called the Quantum Discriminator.
We show that the quantum discriminator can attain 99% accuracy in simulation.
arXiv Detail & Related papers (2020-09-02T19:00:23Z) - Quantum noise protects quantum classifiers against adversaries [120.08771960032033]
Noise in quantum information processing is often viewed as a disruptive and difficult-to-avoid feature, especially in near-term quantum technologies.
We show that by taking advantage of depolarisation noise in quantum circuits for classification, a robustness bound against adversaries can be derived.
This is the first quantum protocol that can be used against the most general adversaries.
arXiv Detail & Related papers (2020-03-20T17:56:14Z) - Statistical Limits of Supervised Quantum Learning [90.0289160657379]
We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning cannot achieve polylogarithmic runtimes in the input dimension.
We conclude that, when no further assumptions on the problem are made, quantum machine learning algorithms for supervised learning can have at most speedups over efficient classical algorithms.
arXiv Detail & Related papers (2020-01-28T17:35:32Z)
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.