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

CREATORRiccardo Molteni, Simon C. Marshall, Vedran Dunjko
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE154 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15964

Browse the full library · About the Tower of Babel