Information-Theoretic Bounds on Quantum Advantage in Machine Learning.

Area of Science:

• Quantum computing
• Machine learning
• Physics

Background:

• Classical and quantum machine learning (ML) models are increasingly used to predict outcomes of physical experiments.
• These experiments involve executing quantum processes (E) with varying input parameters (x).
• The efficiency is measured by the number of quantum process runs required for accurate predictions.

Purpose of the Study:

• To compare the performance of classical and quantum ML models in predicting outcomes of physical experiments.
• To determine scenarios where quantum ML models offer a significant advantage over classical models.
• To understand the potential of classical ML for quantum problems.

Main Methods:

• Analyzing classical ML models that use classical data from quantum process runs.
• Analyzing quantum ML models that leverage coherent access to quantum data.
• Proving theoretical bounds on the number of quantum process runs needed for prediction accuracy.

Main Results:

• Classical ML models can achieve accurate average predictions with a number of runs comparable to optimal quantum ML models for any input distribution.
• Quantum ML models demonstrate an exponential advantage for achieving accurate predictions across all possible inputs.
• Predicting all Pauli observables in an n-qubit system requires 2^Ω(n) copies for classical ML, versus O(n) for quantum ML.

Conclusions:

• Quantum ML models offer an exponential advantage for specific prediction tasks, particularly when accuracy across all inputs is required.
• Classical ML models show competitive performance for average-case predictions, highlighting their utility in certain quantum applications.
• The study clarifies the conditions under which quantum advantage is achievable in ML-driven physical experiments.