Quantum machine learning advantages beyond hardness of evaluation

Understand

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.