Interesting paper on today’s arxiv. 


------------------------------------------------------------------------------

\\
arXiv:2504.15964
Date: Tue, 22 Apr 2025 15:04:46 GMT   (290kb,D)

Title: Quantum machine learning advantages beyond hardness of evaluation
Authors: Riccardo Molteni, Simon C. Marshall, Vedran Dunjko
Categories: quant-ph
Comments: Abstract in the mailings abridged due to characters limit. Please
 refer to the paper for the full abstract
\\
 The most general examples of quantum learning advantages involve data labeled
by cryptographic or intrinsically quantum functions, where classical learners
are limited by the infeasibility of evaluating the labeling functions using
polynomial-sized classical circuits. While broad in scope, such results reveal
little about advantages arising from the learning process itself. In
cryptographic settings, further insight is possible via random-generatability -
the ability to classically generate labeled data - enabling hardness proofs for
identification tasks, where the goal is to identify the labeling function from
a dataset, even when evaluation is classically intractable. These tasks are
particularly relevant in quantum contexts, including Hamiltonian learning and
identifying physically meaningful order parameters. However, for quantum
functions, random-generatability is conjectured not to hold, leaving no known
identification advantages in genuinely quantum regimes.
 In this work, we give the first proofs of quantum identification learning
advantages under standard complexity assumptions. We confirm that quantum-hard
functions are not random-generatable unless BQP is contained in the second
level of the polynomial hierarchy, ruling out cryptographic-style data
generation strategies. We then introduce a new approach: we show that
verifiable identification - solving the identification task for valid datasets
while rejecting invalid ones - is classically hard for quantum labeling
functions unless BQP is in the polynomial hierarchy. Finally, we show that, for
a broad class of tasks, solving the identification problem implies verifiable
identification in the polynomial hierarchy. This yields our main result: a
natural class of quantum identification tasks solvable by quantum learners but
hard for classical learners unless BQP is in the polynomial hierarchy.
\\ ( https://urldefense.com/v3/__https://arxiv.org/abs/2504.15964__;!!D9dNQwwGXtA!QHedr8tvtuxGd5UXW6VpKGzue_sraOD6K-rDrEF6mlrm16TFlxe4bAkVgVsD-atNsTJ5ayDAQTkYePbG58po6A$  ,  290kb)
———————————————————————————————————————

---------------------------------------------------------------------------------
Daniel Manzano
Quantum Thermodynamics and Quantum Computation Group
University of Granada
Facultad de Ciencias, Av. Fuentenueva s/n
Granada 18071, Spain
Phone: +34 958241000  Ext: 20569
https://ic1.ugr.es/members/dmanzano/