Quantum machine learning advantages beyond hardness of evaluation
Riccardo Molteni, Simon C. Marshall, Vedran Dunjko · 2025
Read Quantum machine learning advantages beyond hardness of evaluation by Riccardo Molteni, Simon C. Marshall, Vedran Dunjko (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15964.txt.
Description
Quantum computers may learn some tasks faster than classical ones, but proving where that edge comes from is subtle. Riccardo Molteni, Simon Marshall, and Vedran Dunjko gave new proofs in 2025 about identification tasks, where the goal is to name the function that labeled a dataset. Earlier quantum advantages rested on labeling functions that classical machines cannot even evaluate, which says little about learning itself.
The team show that quantum-hard functions cannot be used to generate labeled data classically, under standard assumptions. They then define a verifiable form of identification and prove it is classically hard for quantum labeling functions. A broad link between the two forms yields the main result for quantum learners.
Catalog record
| CREATOR | Riccardo Molteni, Simon C. Marshall, Vedran Dunjko |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 154 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15964