The No-Free-Lunch (NFL) theorem, which quantifies problem- and
data-independent generalization errors regardless of the optimization process,
provides a foundational framework for comprehending diverse learning protocols'
potential. Despite its significance, the establishment of the NFL theorem for
quantum machine learning models remains largely unexplored, thereby overlooking
broader insights into the fundamental relationship between quantum and
classical learning protocols. To address this gap, we categorize a diverse
array of quantum learning algorithms into three learning protocols designed for
learning quantum dynamics under a specified observable and establish their NFL
theorem. The exploited protocols, namely Classical Learning Protocols
(CLC-LPs), Restricted Quantum Learning Protocols (ReQu-LPs), and Quantum
Learning Protocols (Qu-LPs), offer varying levels of access to quantum
resources. Our derived NFL theorems demonstrate quadratic reductions in sample
complexity across CLC-LPs, ReQu-LPs, and Qu-LPs, contingent upon the
orthogonality of quantum states and the diagonality of observables. We
attribute this performance discrepancy to the unique capacity of
quantum-related learning protocols to indirectly utilize information concerning
the global phases of non-orthogonal quantum states, a distinctive physical
feature inherent in quantum mechanics. Our findings not only deepen our
understanding of quantum learning protocols' capabilities but also provide
practical insights for the development of advanced quantum learning algorithms.

我们将各种量子学习算法按照三种设计的学习协议分类，并建立了其 No-Free-Lunch 定理；我们的研究结果表明量子学习协议在样本复杂度上具有二次降低，这取决于量子态的正交性和观测量的对角性，并深化了对量子学习协议能力的理解。