Entanglement-induced provable and robust quantum learning advantages

Abstract

Quantum computing holds unparalleled potentials to enhance machine learning. However, a demonstration of quantum learning advantage has not been achieved so far. We make a step forward by rigorously establishing a noise-robust, unconditional quantum learning advantage in expressivity, inference speed, and training efficiency, compared to commonly-used classical models. Our proof is information-theoretic and pinpoints the origin of this advantage: entanglement can be used to reduce the communication required by non-local tasks. In particular, we design a task that can be solved with certainty by quantum models with a constant number of parameters using entanglement, whereas commonly-used classical models must scale linearly to achieve a larger-than-exponentially-small accuracy. We show that the quantum model is trainable with constant resources and robust against constant noise. Through numerical and trapped-ion experiments on IonQ Aria, we demonstrate the desired advantage. Our results provide valuable guidance for demonstrating quantum learning advantages with current noisy intermediate-scale devices.

7 pages, 2 figures + 13-page supplementary materials

References in corpus (40)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Bell nonlocality
• Machine learning and the physical sciences
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Quantum support vector machine for big data classification
• Quantum machine learning in feature Hilbert spaces
• First M87 Event Horizon Telescope Results. IV. Imaging the Central Supermassive Black Hole
• Improved Simulation of Stabilizer Circuits
• Quantum principal component analysis
• The effect of data encoding on the expressive power of variational quantum machine learning models
• Challenges and Opportunities in Quantum Machine Learning
• Quantum generative adversarial learning
• A rigorous and robust quantum speed-up in supervised machine learning
• Quantum advantage in learning from experiments
• Quantum machine learning: a classical perspective
• Quantum-enhanced machine learning
• Quantum advantage with shallow circuits
• Provably efficient machine learning for quantum many-body problems
• A quantum-inspired classical algorithm for recommendation systems
• Is quantum advantage the right goal for quantum machine learning?
• Quantum Pseudo-Telepathy
• "All versus nothing" inseparability for two observers
• Quantum advantage with noisy shallow circuits in 3D
• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Quantum federated learning through blind quantum computing
• One qubit as a Universal Approximant
• Non-stabilizerness versus entanglement in matrix product states
• Generative Quantum Learning of Joint Probability Distribution Functions
• Non-IID Quantum Federated Learning with One-shot Communication Complexity
• Interpretable Quantum Advantage in Neural Sequence Learning
• Pseudo-dimension of quantum circuits
• Learning quantum states and unitaries of bounded gate complexity
• Magic-induced computational separation in entanglement theory
• Entanglement-enabled advantage for learning a bosonic random displacement channel
• Empirical Sample Complexity of Neural Network Mixed State Reconstruction
• Accelerating Quantum Algorithms with Precomputation
• MAGIC: Microlensing Analysis Guided by Intelligent Computation