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

2020/07/31 by Kunal Sharma, M. Cerezo, Zoë Holmes +4 · 68 citations
Computer Science · Physics and Astronomy · #Artificial intelligence #Computability, Logic, AI Algorithms #Computer science #Learnability #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum capacity #Quantum discord #Quantum entanglement #Quantum information #Quantum mechanics #Quantum network #Quantum no-deleting theorem #cs.LG #quant-ph

paper · pdf · doi:10.1103/physrevlett.128.070501

published in Physical Review Letters 128(7), 070501 (American Physical Society) · v2: 7+13 pages, 4+2 figures, final version accepted for publication in Physical Review Letters

openalex publication_date 2022/02/18 · arxiv created 2022/02/28 · arxiv updated 2022/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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.

Citations

• Learning representations by back-propagating errors
• Entanglement-assisted guessing of complementary measurement outcomes
• The quest for a Quantum Neural Network
• The space of interactions in neural network models
• A simple formula for the average gate fidelity of a quantum dynamical operation
• Artificial intelligence: a modern approach
• A variational eigenvalue solver on a photonic quantum processor
• Entropic uncertainty relations and their applications
• Quantum Machine Learning
• Quantum Convolutional Neural Networks
• A Universal Training Algorithm for Quantum Deep Learning
• Quantum Computation and Quantum Information
• No Free Lunch for Quantum Machine Learning
• Learning to learn with quantum neural networks via classical neural networks

Cited by

• Absence of Barren Plateaus in Quantum Convolutional Neural Networks