Relation between quantum advantage in supervised learning and quantum computational advantage

• URL: http://arxiv.org/abs/2304.06687v2
• Date: Sat, 1 Jul 2023 07:03:35 GMT
• Title: Relation between quantum advantage in supervised learning and quantum computational advantage
• Authors: Jordi P\'erez-Guijarro, Alba Pag\`es-Zamora and Javier R. Fonollosa
• Abstract summary: Recent work shows that computational and learning advantage are, in general, not equivalent. The existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions. Results are applied to prove that there is a quantum speed-up for some learning tasks based on the prime factorization problem.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The widespread use of machine learning has raised the question of quantum supremacy for supervised learning as compared to quantum computational advantage. In fact, a recent work shows that computational and learning advantage are, in general, not equivalent, i.e., the additional information provided by a training set can reduce the hardness of some problems. This paper investigates under which conditions they are found to be equivalent or, at least, highly related. The existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions. These results are applied to prove that there is a quantum speed-up for some learning tasks based on the prime factorization problem, assuming the classical intractability of this problem.

Related papers

• 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 Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  We study the query complexity of Boolean functions under general higher order quantum computations. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity. We find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
  arXiv  Detail & Related papers  (2023-07-18T13:12:55Z)
• Exponential separations between classical and quantum learners [0.0]
  We discuss how subtle differences in definitions can result in significantly different requirements and tasks for the learner to meet and solve. We present two new learning separations where the classical difficulty primarily lies in identifying the function generating the data.
  arXiv  Detail & Related papers  (2023-06-28T08:55:56Z)
• 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)
• 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)
• Optimal quantum reservoir computing for the NISQ era [0.0]
  In this Letter, we provide a criterion to select optimal quantum reservoirs, requiring few and simple gates. Our findings demonstrate that they render better results than other commonly used models with significantly less gates, and also provide insight on the theoretical gap between quantum reservoir computing and the theory of quantum states complexity.
  arXiv  Detail & Related papers  (2022-05-20T12:00:27Z)
• Experimental violations of Leggett-Garg's inequalities on a quantum computer [77.34726150561087]
  We experimentally observe the violations of Leggett-Garg-Bell's inequalities on single and multi-qubit systems. Our analysis highlights the limits of nowadays quantum platforms, showing that the above-mentioned correlation functions deviate from theoretical prediction as the number of qubits and the depth of the circuit grow.
  arXiv  Detail & Related papers  (2021-09-06T14:35:15Z)
• Quantum advantage for differential equation analysis [13.39145467249857]
  We show how the output of quantum differential equation solving can serve as the input for quantum machine learning. These quantum algorithms provide an exponential advantage over existing classical Monte Carlo methods.
  arXiv  Detail & Related papers  (2020-10-29T17:19:04Z)
• Experimental demonstration of quantum advantage for NP verification with limited information [4.6453787256723365]
  We show an experimental demonstration of a quantum computational advantage in a prover-verifier interactive setting. We provide a simple linear optical implementation that can perform this verification task efficiently. We also provide strong evidence that, fixing the size of the proof, a classical computer would take much longer time.
  arXiv  Detail & Related papers  (2020-07-31T07:14:13Z)
• 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)
• 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.