# Revisiting dequantization and quantum advantage in learning tasks

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 16 references that are in the map.
- First posted on arXiv 1 Dec 2021.

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

- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (2021)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning](https://mlsanity.com/paper/1910.06151/) (2019)
- [Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension](https://mlsanity.com/paper/1811.04909/) (2018)

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

- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Group-Invariant Quantum Machine Learning](https://mlsanity.com/paper/2205.02261/) (2022)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance](https://mlsanity.com/paper/2401.11351/) (2024)
- [Quantum-Inspired Machine Learning: a Survey](https://mlsanity.com/paper/2308.11269/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [SnCQA: A hardware-efficient equivariant quantum convolutional circuit architecture](https://mlsanity.com/paper/2211.12711/) (2022)
- [Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms](https://mlsanity.com/paper/2304.04932/) (2023)
- [Covariance matrix preparation for quantum principal component analysis](https://mlsanity.com/paper/2204.03495/) (2022)
- [A Parameter-Efficient Quantum Anomaly Detection Method on a Superconducting Quantum Processor](https://mlsanity.com/paper/2412.16867/) (2024)
- [Provable and scalable quantum Gaussian processes for quantum learning](https://mlsanity.com/paper/2605.00099/) (2026)
- [Optimisation-free Classification and Density Estimation with Quantum Circuits](https://mlsanity.com/paper/2203.14452/) (2022)

## Abstract (arXiv)

It has been shown that the apparent advantage of some quantum machine learning algorithms may be efficiently replicated using classical algorithms with suitable data access -- a process known as dequantization. Existing works on dequantization compare quantum algorithms which take copies of an n-qubit quantum state |xrangle = sumi xi |irangle as input to classical algorithms which have sample and query (SQ) access to the vector x. In this note, we prove that classical algorithms with SQ access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs. Because classical algorithms are a subset of quantum algorithms, this demonstrates that SQ access can sometimes be significantly more powerful than quantum state inputs. Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs. If we compare quantum algorithms with quantum state inputs to classical algorithms with access to measurement data on quantum states, the landscape of quantum advantage can be dramatically different. We remark that when the quantum states are constructed from exponential-size classical data, comparing SQ access and quantum state inputs is appropriate since both require exponential time to prepare.