Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets

Abstract

The no-free-lunch (NFL) theorem is a celebrated result in learning theory that limits one's ability to learn a function with a training data set. With the recent rise of quantum machine learning, it is natural to ask whether there is a quantum analog of the NFL theorem, which would restrict a quantum computer's ability to learn a unitary process (the quantum analog of a function) with quantum training data. However, in the quantum setting, the training data can possess entanglement, a strong correlation with no classical analog. In this work, we show that entangled data sets lead to an apparent violation of the (classical) NFL theorem. This motivates a reformulation that accounts for the degree of entanglement in the training set. As our main result, we prove a quantum NFL theorem whereby the fundamental limit on the learnability of a unitary is reduced by entanglement. We employ Rigetti's quantum computer to test both the classical and quantum NFL theorems. Our work establishes that entanglement is a commodity in quantum machine learning.

v2: 7+13 pages, 4+2 figures, final version accepted for publication in Physical Review Letters

References in corpus (11)

• The quest for a Quantum Neural Network
• Quantum-enhanced machine learning
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Layerwise learning for quantum neural networks
• Trainability of Dissipative Perceptron-Based Quantum Neural Networks
• Large gradients via correlation in random parameterized quantum circuits
• Variational Quantum State Eigensolver
• Learning to learn with quantum neural networks via classical neural networks
• Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets
• Quantum walks on graphs representing the firing patterns of a quantum neural network
• No Free Lunch for Quantum Machine Learning

Cited by in corpus (32)

• Challenges and Opportunities in Quantum Machine Learning
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Generalization in quantum machine learning from few training data
• Absence of Barren Plateaus in Quantum Convolutional Neural Networks
• Information-theoretic bounds on quantum advantage in machine learning
• Trainability of Dissipative Perceptron-Based Quantum Neural Networks
• Quantum Machine Learning for Chemistry and Physics
• Barren plateaus preclude learning scramblers
• Recent advances for quantum classifiers
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Out-of-distribution generalization for learning quantum dynamics
• Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets
• Analytic theory for the dynamics of wide quantum neural networks
• Variational Hamiltonian Diagonalization for Dynamical Quantum Simulation
• Variational inference with a quantum computer
• Overfitting in quantum machine learning and entangling dropout
• Long-time simulations with high fidelity on quantum hardware
• Universal Adversarial Examples and Perturbations for Quantum Classifiers
• Dynamical simulation via quantum machine learning with provable generalization
• Variational Quantum Approximate Support Vector Machine with Inference Transfer
• Learning quantum states and unitaries of bounded gate complexity
• Entangled Datasets for Quantum Machine Learning
• Entanglement entropy production in Quantum Neural Networks
• Architectural Vision for Quantum Computing in the Edge-Cloud Continuum
• Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metric
• Impossibility Results in AI: A Survey
• Optimal quantum dataset for learning a unitary transformation
• Transition Role of Entangled Data in Quantum Machine Learning
• Quantum Continual Learning Overcoming Catastrophic Forgetting
• The power and limitations of learning quantum dynamics incoherently
• Topological Learning in Multi-Class Data Sets
• Measuring Incompatible Observables with Quantum Neural Networks