# Advantage of Quantum Machine Learning from General Computational Advantages

arXiv: https://arxiv.org/abs/2312.03057 · HTML: https://mlsanity.com/paper/2312.03057/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 89 references that are in the map.
- First posted on arXiv 5 Dec 2023.

## Builds on (most cited first, 21 of 21)

- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Differentiable Learning of Quantum Circuit Born Machine](https://mlsanity.com/paper/1804.04168/) (2018)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Exponential separations between classical and quantum learners](https://mlsanity.com/paper/2306.16028/) (2023)
- [Quantum assisted Gaussian process regression](https://mlsanity.com/paper/1512.03929/) (2015)
- [On establishing learning separations between classical and quantum machine learning with classical data](https://mlsanity.com/paper/2208.06339/) (2022)
- [Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions](https://mlsanity.com/paper/2004.10756/) (2020)
- [Towards quantum advantage via topological data analysis](https://mlsanity.com/paper/2005.02607/) (2020)
- [Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation](https://mlsanity.com/paper/2301.11936/) (2023)
- [Exponential Error Convergence in Data Classification with Optimized Random Features: Acceleration by Quantum Machine Learning](https://mlsanity.com/paper/2106.09028/) (2021)
- [Topological data analysis on noisy quantum computers](https://mlsanity.com/paper/2209.09371/) (2022)
- [Quantum Persistent Homology for Time Series](https://mlsanity.com/paper/2211.04465/) (2022)

## Built on by (most cited first, 4 of 4)

- [Benchmarking MedMNIST dataset on real quantum hardware](https://mlsanity.com/paper/2502.13056/) (2025)
- [A Quantum-Inspired Dequantization Method for Diagonally Weighted Matrix Functions: Application to Learning with Optimized Random Features](https://mlsanity.com/paper/2609.10729/) (2026)
- [Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries](https://mlsanity.com/paper/2609.38403/) (2026)
- [Classical Hardness of Learning Functions of Hamiltonians](https://mlsanity.com/paper/2610.01141/) (2026)

## Abstract (arXiv)

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 with 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 open routes to exploit a variety of quantum advantages in computing functions for the experimental demonstration of the advantage of QML.