量子ニューラルネットワークの新しい「No-Free-Lunch定理」が、量子高速化への希望を与える New No-Free-Lunch theorem for quantum neural networks gives hope for quantum speedup
2022-03-24 ロスアラモス国立研究所（LANL）
・これまで、量子ニューラルネットワークを学習させるには指数関数的に大きな学習セットが必要だと考えていましたが、ロスアラモス国立研究所が開発した「No-Free-Lunch定理」により、量子もつれがこの指数関数的なオーバーヘッドをなくすことが示された。
・「私たちの研究は、量子機械学習において、大きなデータと大きなエンタングルメントの両方が貴重であることを証明しており、エンタングルメントはスケーラビリティにつながり、学習するためにデータのサイズを指数関数的に大きくするという障害を解決します」と、ロスアラモスのAndrew Sornborgerは述べています。
＜関連情報＞
- https://discover.lanl.gov/news/0223-quantum-machine-learning
- https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.128.070501
絡み合ったデータセットに対する「No-Free-Lunch定理」の再定式化 Reformulation of the No-Free-Lunch Theorem for Entangled Datasets
Kunal Sharma, M. Cerezo, Zoë Holmes, Lukasz Cincio, Andrew Sornborger, and Patrick J. Coles
Published 18 February 2022 DOI:https://doi.org/10.1103/PhysRevLett.128.070501
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 dataset. 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 with quantum training data. However, in the quantum setting, the training data can possess entanglement, a strong correlation with no classical analog. In this Letter, we show that entangled datasets 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 Letter establishes that entanglement is a commodity in quantum machine learning.
