Statistical Limits of Supervised Quantum Learning

• URL: http://arxiv.org/abs/2001.10477v3
• Date: Thu, 29 Oct 2020 09:36:24 GMT
• Title: Statistical Limits of Supervised Quantum Learning
• Authors: Carlo Ciliberto, Andrea Rocchetto, Alessandro Rudi, Leonard Wossnig
• Abstract summary: 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.
• Score: 90.0289160657379
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Within the framework of statistical learning theory it is possible to bound the minimum number of samples required by a learner to reach a target accuracy. We show that if the bound on the accuracy is taken into account, quantum machine learning algorithms for supervised learning---for which statistical guarantees are available---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 polynomial speedups over efficient classical algorithms, even in cases where quantum access to the data is naturally available.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• 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)
• Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness [0.0]
  We show the natural robustness of quantum statistical queries for learning quantum processes. We adapt a learning algorithm for constant-depth quantum circuits to the quantum statistical query setting. We prove that pseudorandom unitaries (PRUs) cannot be constructed using circuits of constant depth.
  arXiv  Detail & Related papers  (2024-05-20T14:55:20Z)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Learning unitaries with quantum statistical queries [0.0]
  We propose several algorithms for learning unitary operators from quantum statistical queries (QSQs) Our methods hinge on a novel technique for estimating the Fourier mass of a unitary on a subset of Pauli strings with a single quantum statistical query. We show that quantum statistical queries lead to an exponentially larger sample complexity for certain tasks, compared to separable measurements to the Choi-Jamiolkowski state.
  arXiv  Detail & Related papers  (2023-10-03T17:56:07Z)
• Statistical Complexity of Quantum Learning [32.48879688084909]
  This article reviews the complexity of quantum learning using information-theoretic techniques. We focus on data complexity, copy complexity, and model complexity. We highlight the differences between quantum and classical learning by addressing both supervised and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-20T20:04:05Z)
• 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)
• On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
  We devise three effective QAE-based learning protocols to address three classically computational hard learning problems. Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
  arXiv  Detail & Related papers  (2021-06-29T14:01:40Z)
• Power of data in quantum machine learning [2.1012068875084964]
  We show that some problems that are classically hard to compute can be easily predicted by classical machines learning from data. We propose a projected quantum model that provides a simple and rigorous quantum speed-up for a learning problem in the fault-tolerant regime.
  arXiv  Detail & Related papers  (2020-11-03T19:00:01Z)
• A rigorous and robust quantum speed-up in supervised machine learning [6.402634424631123]
  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.
  arXiv  Detail & Related papers  (2020-10-05T17:22:22Z)

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.