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:2208.06339

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

Casper Gyurik, Vedran Dunjko

Published Aug 12, 2022• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2208.06339

Related papers

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

Exponential quantum advantages in learning quantum observables from classical data

Riccardo Molteni, Casper Gyurik, Vedran Dunjko

Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that $$BQP$$ B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.

arXiv:2405.02027•npj Quantum Information•Jan 10, 2026•6 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

Hybrid Quantum-Classical Frameworks in AI: Challenges, Trends, and Opportunities

Nidhi Arora, Dinesh Kumar, Ashok Sharma +2 more

Over the past several decades, computing has undergone revolutionary changes, moving beyond classical systems that manipulate ones and zeroes to solve complex problems. One key area where quantum computing power is particularly promising is machine learning. While conventional machine learning algorithms have successfully addressed a diverse set of challenges, they are often computationally intensive and slow, while working on today's massive datasets. Quantum machine learning aims to solve these challenges by enhancing classical methods with quantum algorithms, offering faster processing and more efficient data analysis. In recent years, research has focused on applying quantum techniques to classic machine learning tasks. This paper reviews key contributions from researchers in quantum machine learning and explores its potential to revolutionize real-world problem-solving by integrating both traditional and quantum methods.

CRC Press eBooks•May 8, 2026•0 citations

Quantum Machine Learning—An Overview

Kyriaki A. Tychola, Τheofanis Kalampokas, George A. Papakostas

Quantum computing has been proven to excel in factorization issues and unordered search problems due to its capability of quantum parallelism. This unique feature allows exponential speed-up in solving certain problems. However, this advantage does not apply universally, and challenges arise when combining classical and quantum computing to achieve acceleration in computation speed. This paper aims to address these challenges by exploring the current state of quantum machine learning and benchmarking the performance of quantum and classical algorithms in terms of accuracy. Specifically, we conducted experiments with three datasets for binary classification, implementing Support Vector Machine (SVM) and Quantum SVM (QSVM) algorithms. Our findings suggest that the QSVM algorithm outperforms classical SVM on complex datasets, and the performance gap between quantum and classical models increases with dataset complexity, as simple models tend to overfit with complex datasets. While there is still a long way to go in terms of developing quantum hardware with sufficient resources, quantum machine learning holds great potential in areas such as unsupervised learning and generative models. Moving forward, more efforts are needed to explore new quantum learning models that can leverage the power of quantum mechanics to overcome the limitations of classical machine learning.

Electronics•May 24, 2023•118 citations

From Classical to Quantum: Evaluating Machine Learning Enhancements

A. Senthilselvi, S Narendrakumar, G V Madhav Ram Samanvay +3 more

Quantum computing has been a source of hype in the past few years—especially in its application to machine learning (ML) use-cases. This paper compares QML algorithms to traditional ML for a variety of classification problems yielding an overview on potential applications that quantum technologies can either complement or provide superior performance. The paper begins by outlining the fundamental principles of quantum computing required for its application in machine learning. This article will highlight key ideas such as quantum parallelism and the use of quantum interference in n-computing efficiency. The conversation turns to Quantum machine learning Algorithms, in comparison with Classical algorithms without any further ado and specific quantum algorithmic extensions which are available for the problem of machines. These quantum algorithms are analyzed in terms of computational speed and accuracy, leveraging qubits to potentially accelerate learning processes and achieve improved results. Both the prospects and challenges of quantum algorithms for practical ML applications, by combining empirical data with insights from theory. The study also investigates how these limitations of quantum computing today such as qubit coherence, error rates and scalability are likely to impact the practical deployment of QML. In the final sections, the paper discusses next steps and future directions for quantum machine learning with a focus on potential milestones that could lift current obstacles to merge more deeply classical and quantum tools of data analysis. The article provides an in-depth data-driven perspective on the emerging intersection of these two fields with a view towards their potential future impact within quantum machine learning.

International Conference on Advances in Computation, Communication and Information Technology (ICAICCIT)•Nov 28, 2024•10 citations
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.
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.
Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that BQPBQPBQP B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.
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.
Over the past several decades, computing has undergone revolutionary changes, moving beyond classical systems that manipulate ones and zeroes to solve complex problems. One key area where quantum computing power is particularly promising is machine learning. While conventional machine learning algorithms have successfully addressed a diverse set of challenges, they are often computationally intensive and slow, while working on today's massive datasets. Quantum machine learning aims to solve these challenges by enhancing classical methods with quantum algorithms, offering faster processing and more efficient data analysis. In recent years, research has focused on applying quantum techniques to classic machine learning tasks. This paper reviews key contributions from researchers in quantum machine learning and explores its potential to revolutionize real-world problem-solving by integrating both traditional and quantum methods.
Quantum computing has been proven to excel in factorization issues and unordered search problems due to its capability of quantum parallelism. This unique feature allows exponential speed-up in solving certain problems. However, this advantage does not apply universally, and challenges arise when combining classical and quantum computing to achieve acceleration in computation speed. This paper aims to address these challenges by exploring the current state of quantum machine learning and benchmarking the performance of quantum and classical algorithms in terms of accuracy. Specifically, we conducted experiments with three datasets for binary classification, implementing Support Vector Machine (SVM) and Quantum SVM (QSVM) algorithms. Our findings suggest that the QSVM algorithm outperforms classical SVM on complex datasets, and the performance gap between quantum and classical models increases with dataset complexity, as simple models tend to overfit with complex datasets. While there is still a long way to go in terms of developing quantum hardware with sufficient resources, quantum machine learning holds great potential in areas such as unsupervised learning and generative models. Moving forward, more efforts are needed to explore new quantum learning models that can leverage the power of quantum mechanics to overcome the limitations of classical machine learning.
Quantum computing has been a source of hype in the past few years—especially in its application to machine learning (ML) use-cases. This paper compares QML algorithms to traditional ML for a variety of classification problems yielding an overview on potential applications that quantum technologies can either complement or provide superior performance. The paper begins by outlining the fundamental principles of quantum computing required for its application in machine learning. This article will highlight key ideas such as quantum parallelism and the use of quantum interference in n-computing efficiency. The conversation turns to Quantum machine learning Algorithms, in comparison with Classical algorithms without any further ado and specific quantum algorithmic extensions which are available for the problem of machines. These quantum algorithms are analyzed in terms of computational speed and accuracy, leveraging qubits to potentially accelerate learning processes and achieve improved results. Both the prospects and challenges of quantum algorithms for practical ML applications, by combining empirical data with insights from theory. The study also investigates how these limitations of quantum computing today such as qubit coherence, error rates and scalability are likely to impact the practical deployment of QML. In the final sections, the paper discusses next steps and future directions for quantum machine learning with a focus on potential milestones that could lift current obstacles to merge more deeply classical and quantum tools of data analysis. The article provides an in-depth data-driven perspective on the emerging intersection of these two fields with a view towards their potential future impact within quantum machine learning.