Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2304.06687 · IEEE Transactions on Quantum Engineering

Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage

Jordi Pérez-Guijarro, Alba Pagés-Zamora, J.R. Fonollosa

Published Dec 26, 2023• 5 citations
arXivHTMLPDF

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. This relation is analyzed by considering two definitions of learning speed-up: one tied to the distribution and another that is distribution-independent. In both cases, the existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions, although, for the distribution-independent definition, additional mild conditions must also be met. Finally, 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.

DOI
10.1109/tqe.2023.3347476

Related papers

Advantage of quantum machine learning from general computational advantages

Hayata Yamasaki, Natsuto Isogai, Mio Murao

An overarching milestone of quantum machine learning (QML) is to demonstrate the advantage of QML over all possible classical learning methods in accelerating a common type of learning task, as represented by supervised learning from classical data. However, the provable advantages of QML in supervised learning have been known so far only for the learning tasks designed for using the advantage of specific quantum algorithms, i.e., Shor’s algorithms. Here, we explicitly construct an unprecedentedly broader family of supervised learning tasks with classical data to offer the provable advantage of QML based on general quantum computational advantages, progressing beyond Shor’s algorithms. Our learning task is feasibly achievable by executing a general class of functions that can be computed efficiently in polynomial time for a large fraction of inputs by arbitrary quantum algorithms, but not by any classical algorithm. We prove the hardness of achieving this learning task for any possible polynomial-time classical learning method. We also clarify protocols for preparing the classical data to demonstrate this learning task in experiments. These results provide a way to exploit a variety of quantum advantages in computing functions for the realization of provably advantageous QML.

arXiv:2312.03057•npj Quantum Information•Jul 28, 2026•2 citations

On establishing learning separations between classical and quantum machine learning with classical data

Casper Gyurik, Vedran Dunjko

Despite years of effort, the quantum machine learning community has only been able to show quantum learning advantages for certain contrived cryptography-inspired datasets in the case of classical data. In this note, we discuss the challenges of finding learning problems that quantum learning algorithms can learn much faster than any classical learning algorithm, and we study how to identify such learning problems. Specifically, we reflect on the main concepts in computational learning theory pertaining to this question, and we discuss how subtle changes in definitions can mean conceptually significantly different tasks, which can either lead to a separation or no separation at all. Moreover, we study existing learning problems with a provable quantum speedup to distill sets of more general and sufficient conditions (i.e., ``checklists'') for a learning problem to exhibit a separation between classical and quantum learners. These checklists are intended to streamline one's approach to proving quantum speedups for learning problems, or to elucidate bottlenecks. Finally, to illustrate its application, we analyze examples of potential separations (i.e., when the learning problem is build from computational separations, or when the data comes from a quantum experiment) through the lens of our approach.

arXiv:2208.06339•Aug 12, 2022•8 citations

Comparisons of performance between quantum-enhanced and classical machine learning algorithms on the IBM Quantum Experience

Pavlo V. Zahorodko, Serhiy O. Semerikov, Vladimir Soloviev +3 more

Abstract Machine learning is now widely used almost everywhere, primarily for forecasting. In the broadest sense, the machine learning objective may be summarized as an approximation problem, and the issues solved by various training methods can be reduced to finding the optimal value of an unknown function or restoring a function. At the moment, we have only experimental samples of quantum computers based on classical-quantum logic, when quantum gates are used instead of ordinary logic gates, and probabilistic quantum bits are used instead of deterministic bits. Namely, the probabilistic nature problems that provide for the determination of a certain optimal state from a large set of possible ones on which quantum computers can achieve “quantum supremacy” – an extraordinary (by many orders of magnitude) reduction in the time required to solve the task. The main idea of the work is to identify the possibility of achieving, if not quantum supremacy, then at least a quantum advantage when solving machine learning problems on a quantum computer.

Journal of Physics Conference Series•Mar 1, 2021•31 citations

Exponential separations between classical and quantum learners

Casper Gyurik, Vedran Dunjko

Despite significant effort, the quantum machine learning community has only demonstrated quantum learning advantages for artificial cryptography-inspired datasets when dealing with classical data. In this paper we address the challenge of finding learning problems where quantum learning algorithms can achieve a provable exponential speedup over classical learning algorithms. We reflect on computational learning theory concepts related to this question and discuss how subtle differences in definitions can result in significantly different requirements and tasks for the learner to meet and solve. We examine existing learning problems with provable quantum speedups and find that they largely rely on the classical hardness of evaluating the function that generates the data, rather than identifying it. To address this, we present two new learning separations where the classical difficulty primarily lies in identifying the function generating the data. Furthermore, we explore computational hardness assumptions that can be leveraged to prove quantum speedups in scenarios where data is quantum-generated, which implies likely quantum advantages in a plethora of more natural settings (e.g., in condensed matter and high energy physics). We also discuss the limitations of the classical shadow paradigm in the context of learning separations, and how physically-motivated settings such as characterizing phases of matter and Hamiltonian learning fit in the computational learning framework.

arXiv:2306.16028•Jun 28, 2023•9 citations

Quantum Semi-Supervised Learning with Quantum Supremacy

Zhou Shangnan

Quantum machine learning promises to efficiently solve important problems. There are two persistent challenges in classical machine learning: the lack of labeled data, and the limit of computational power. We propose a novel framework that resolves both issues: quantum semi-supervised learning. Moreover, we provide a protocol in systematically designing quantum machine learning algorithms with quantum supremacy, which can be extended beyond quantum semi-supervised learning. In the meantime, we show that naive quantum matrix product estimation algorithm outperforms the best known classical matrix multiplication algorithm. We showcase two concrete quantum semi-supervised learning algorithms: a quantum self-training algorithm named the propagating nearest-neighbor classifier, and the quantum semi-supervised K-means clustering algorithm. By doing time complexity analysis, we conclude that they indeed possess quantum supremacy.

arXiv:2110.02343•Oct 5, 2021•5 citations

Quantum machine learning: a classical perspective

Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo +4 more

Recently, increased computational power and data availability, as well as algorithmic advances, have led machine learning (ML) techniques to impressive results in regression, classification, data generation and reinforcement learning tasks. Despite these successes, the proximity to the physical limits of chip fabrication alongside the increasing size of datasets is motivating a growing number of researchers to explore the possibility of harnessing the power of quantum computation to speed up classical ML algorithms. Here we review the literature in quantum ML and discuss perspectives for a mixed readership of classical ML and quantum computation experts. Particular emphasis will be placed on clarifying the limitations of quantum algorithms, how they compare with their best classical counterparts and why quantum resources are expected to provide advantages for learning problems. Learning in the presence of noise and certain computationally hard problems in ML are identified as promising directions for the field. Practical questions, such as how to upload classical data into quantum form, will also be addressed.

arXiv:1707.08561•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jan 1, 2018•518 citations
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. This relation is analyzed by considering two definitions of learning speed-up: one tied to the distribution and another that is distribution-independent. In both cases, the existence of efficient algorithms to generate training sets emerges as the cornerstone of such conditions, although, for the distribution-independent definition, additional mild conditions must also be met. Finally, 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.
An overarching milestone of quantum machine learning (QML) is to demonstrate the advantage of QML over all possible classical learning methods in accelerating a common type of learning task, as represented by supervised learning from classical data. However, the provable advantages of QML in supervised learning have been known so far only for the learning tasks designed for using the advantage of specific quantum algorithms, i.e., Shor’s algorithms. Here, we explicitly construct an unprecedentedly broader family of supervised learning tasks with classical data to offer the provable advantage of QML based on general quantum computational advantages, progressing beyond Shor’s algorithms. Our learning task is feasibly achievable by executing a general class of functions that can be computed efficiently in polynomial time for a large fraction of inputs by arbitrary quantum algorithms, but not by any classical algorithm. We prove the hardness of achieving this learning task for any possible polynomial-time classical learning method. We also clarify protocols for preparing the classical data to demonstrate this learning task in experiments. These results provide a way to exploit a variety of quantum advantages in computing functions for the realization of provably advantageous QML.
Despite years of effort, the quantum machine learning community has only been able to show quantum learning advantages for certain contrived cryptography-inspired datasets in the case of classical data. In this note, we discuss the challenges of finding learning problems that quantum learning algorithms can learn much faster than any classical learning algorithm, and we study how to identify such learning problems. Specifically, we reflect on the main concepts in computational learning theory pertaining to this question, and we discuss how subtle changes in definitions can mean conceptually significantly different tasks, which can either lead to a separation or no separation at all. Moreover, we study existing learning problems with a provable quantum speedup to distill sets of more general and sufficient conditions (i.e., ``checklists'') for a learning problem to exhibit a separation between classical and quantum learners. These checklists are intended to streamline one's approach to proving quantum speedups for learning problems, or to elucidate bottlenecks. Finally, to illustrate its application, we analyze examples of potential separations (i.e., when the learning problem is build from computational separations, or when the data comes from a quantum experiment) through the lens of our approach.
Abstract Machine learning is now widely used almost everywhere, primarily for forecasting. In the broadest sense, the machine learning objective may be summarized as an approximation problem, and the issues solved by various training methods can be reduced to finding the optimal value of an unknown function or restoring a function. At the moment, we have only experimental samples of quantum computers based on classical-quantum logic, when quantum gates are used instead of ordinary logic gates, and probabilistic quantum bits are used instead of deterministic bits. Namely, the probabilistic nature problems that provide for the determination of a certain optimal state from a large set of possible ones on which quantum computers can achieve “quantum supremacy” – an extraordinary (by many orders of magnitude) reduction in the time required to solve the task. The main idea of the work is to identify the possibility of achieving, if not quantum supremacy, then at least a quantum advantage when solving machine learning problems on a quantum computer.
Despite significant effort, the quantum machine learning community has only demonstrated quantum learning advantages for artificial cryptography-inspired datasets when dealing with classical data. In this paper we address the challenge of finding learning problems where quantum learning algorithms can achieve a provable exponential speedup over classical learning algorithms. We reflect on computational learning theory concepts related to this question and discuss how subtle differences in definitions can result in significantly different requirements and tasks for the learner to meet and solve. We examine existing learning problems with provable quantum speedups and find that they largely rely on the classical hardness of evaluating the function that generates the data, rather than identifying it. To address this, we present two new learning separations where the classical difficulty primarily lies in identifying the function generating the data. Furthermore, we explore computational hardness assumptions that can be leveraged to prove quantum speedups in scenarios where data is quantum-generated, which implies likely quantum advantages in a plethora of more natural settings (e.g., in condensed matter and high energy physics). We also discuss the limitations of the classical shadow paradigm in the context of learning separations, and how physically-motivated settings such as characterizing phases of matter and Hamiltonian learning fit in the computational learning framework.
Quantum machine learning promises to efficiently solve important problems. There are two persistent challenges in classical machine learning: the lack of labeled data, and the limit of computational power. We propose a novel framework that resolves both issues: quantum semi-supervised learning. Moreover, we provide a protocol in systematically designing quantum machine learning algorithms with quantum supremacy, which can be extended beyond quantum semi-supervised learning. In the meantime, we show that naive quantum matrix product estimation algorithm outperforms the best known classical matrix multiplication algorithm. We showcase two concrete quantum semi-supervised learning algorithms: a quantum self-training algorithm named the propagating nearest-neighbor classifier, and the quantum semi-supervised K-means clustering algorithm. By doing time complexity analysis, we conclude that they indeed possess quantum supremacy.
Recently, increased computational power and data availability, as well as algorithmic advances, have led machine learning (ML) techniques to impressive results in regression, classification, data generation and reinforcement learning tasks. Despite these successes, the proximity to the physical limits of chip fabrication alongside the increasing size of datasets is motivating a growing number of researchers to explore the possibility of harnessing the power of quantum computation to speed up classical ML algorithms. Here we review the literature in quantum ML and discuss perspectives for a mixed readership of classical ML and quantum computation experts. Particular emphasis will be placed on clarifying the limitations of quantum algorithms, how they compare with their best classical counterparts and why quantum resources are expected to provide advantages for learning problems. Learning in the presence of noise and certain computationally hard problems in ML are identified as promising directions for the field. Practical questions, such as how to upload classical data into quantum form, will also be addressed.