A rigorous and robust quantum speed-up in supervised machine learning

By Yunchao Liu, Srinivasan Arunachalam, Kristan Temme. Nature Physics, 2020

765 citations recorded by the source corpus.

Recently, several quantum machine learning algorithms have been proposed that may offer quantum speed-ups over their classical counterparts. Most of these algorithms are either heuristic or assume that data can be accessed quantum-mechanically, making it unclear whether a quantum advantage can be proven without resorting to strong assumptions. Here we construct a classification problem with which we can rigorously show that heuristic quantum kernel methods can provide an end-to-end quantum speed-up with only classical access to data. To prove the quantum speed-up, we construct a family of datasets and show that no classical learner can classify the data inverse-polynomially better than random guessing, assuming the widely believed hardness of the discrete logarithm problem. Furthermore, we construct a family of parameterized unitary circuits, which can be efficiently implemented on a fault-tolerant quantum computer, and use them to map the data samples to a quantum feature space and estimate the kernel entries. The resulting quantum classifier achieves high accuracy and is robust against additive errors in the kernel entries that arise from finite sampling statistics. Many quantum machine learning algorithms have been proposed, but it is typically unknown whether they would outperform classical methods on practical devices. A specially constructed algorithm shows that a formal quantum advantage is possible.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/0352ab40731384f97a7211757981a1fb20a6abd5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Challenges and opportunities in quantum machine learning (2022, background): “[27] Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme, “A rigorous and robust quantum speed-up in supervised machine learning,” Nature Physics , 1–5 (2021).”
The future of quantum computing with superconducting qubits (2022, methodology): “Quantum kernel methods have also been found that lead to provable speedups 101 and expand to a class of kernels for data with group structure 102 .”
Barren plateaus in variational quantum computing (2024, neutral): “Finally, as these are the most common BPs discussed in this Review, in what follows, we assume BPs to be probabilistic unless stated otherwise.”