Transition role of entangled data in quantum machine learning

The paper investigates how the degree of entanglement in training data (quantified by Schmidt rank r) influences the performance of quantum machine learning models for learning quantum dynamics. While entanglement is key to quantum advantage and prior works have shown benefits from entangled operations or measurements, the role of entangled input states (entangled data) has been underexplored. Leveraging the no-free-lunch (NFL) framework from machine learning, the authors aim to analytically characterize whether and when entangled data reduce prediction error or sample complexity. They establish a quantum NFL theorem showing a transition behavior: entangled data help when enough measurement resources are available, but can hurt when measurements are limited. This addresses the practical need to design QML protocols under resource constraints typical of early-stage quantum devices.

The study situates itself within quantum algorithms that leverage entanglement for cryptography and optimization, and within QML efforts that show advantages in learning quantum dynamics via entangled operations or measurements. Prior quantum NFL theorems either considered different learning settings or assumed infinite query complexity, leaving open the impact of entangled input data under realistic (finite) measurements. Related works on information-theoretic bounds for learning quantum dynamics, shadow-based learning, and state/process learning have analyzed sample and query complexity, often attributing benefits to entanglement in data or measurements. However, these works did not resolve the trade-offs when measurement access is limited, nor did they explicitly analyze how Schmidt rank in training data affects prediction error in incoherent learning. The present work bridges these gaps, connecting to classical NFL insights about dependence on data size and type, and refining quantum lower bounds by accounting for Schmidt rank and mutual information analyses beyond Holevo-type bounds.

Problem setup: The task is to learn quantum dynamics of an n-qubit unitary U under a fixed observable O (primarily projective O = |0⟩⟨0|), predicting f_U(ψ) = Tr(O U|ψ⟩⟨ψ|U†). The learner builds a hypothesis unitary V_S from training data S to approximate f_U. Input states may be entangled with a reference system; all inputs have the same Schmidt rank r ∈ {1, …, 2^n}. Each training example (|ψ_i⟩, o_i) comprises an entangled input and an empirical response o_i obtained from m projective measurements of O on U|ψ_i⟩. Sample complexity is N (number of input states), and query complexity is Nm. Performance is measured by the average squared prediction error (risk) R_U(V_S) = ∫ dμ(|f_U(ψ) − h_S(ψ)|^2), averaging over Haar-distributed states; Haar unitaries are used as targets, with input states sampled to approximate uniform entangled states with Schmidt rank r. Core theoretical results: Theorem 1 (informal) provides a lower bound on the averaged prediction error for incoherent learning with finite measurements. Assuming small training error ε ≈ 2^{-n}, the bound exhibits a minimum term that depends on r, N, and m, revealing a dual (transition) role of entanglement. When measurements are sufficient such that r < m/(c1 2^n n), increasing r decreases prediction error (or required N); in extremes, r = 1 requires N ≈ 2^n c2 / n to reach zero averaged risk, whereas r = 2^n needs only N = 1. Conversely, if r ≥ m/(c1 2^n n), increasing r can increase prediction error. The bound also implies that beyond m ≥ r c1 2^n n, further increasing m does not reduce error; at least r^2 c1 2^n n measurements are needed to fully exploit entangled data. The minimal query complexity to achieve zero risk scales as Nm = O(4^n r c1 c2), matching optimal lower bounds for quantum state tomography with nonadaptive measurements in this setting and improving on prior bounds that used coarser information limits. Generalized measurement setting: Theorem 2 extends to arbitrary observables O (‖O‖ ≤ 1) and l-outcome POVMs for data collection. It shows the transition persists under generic measurements and that increasing the number of POVM outcomes l can exponentially reduce the measurement/query complexity needed for a given error level. In extreme cases, constant l yields query complexity ~ 2^n r log(|χ2(O)|), while l = 2^n reduces it to ~ r log(|χ2(O)|). Proof approach: The lower bound is established via Fano’s method. (I) Discretize the unitary space into a 2^r-packing M_{2^r} under a metric tied to O, ensuring distinguishability. (II) Reduce dynamics learning to a hypothesis testing problem where Alice encodes an index X in U_X and measurement data S; Bob estimates X from S. The average prediction error is lower bounded by the misclassification probability P(X ≠ X̂). (III) Apply Fano’s inequality to lower bound P(X ≠ X̂) using the packing cardinality and an upper bound on mutual information I(X; X̂). The latter is bounded in two regimes: for small m using KL divergences among output distributions, yielding I = O(N m d^2 / r) on average; and for large m by I ≤ O(r n), independent of m, reflecting the maximal extractable information from states. Taking the minimum of these bounds yields the transition behavior in r. Numerical simulations: For n = 4 qubits and projective O = |0⟩⟨0|^{⊗n}, target unitaries U_i are chosen from a discrete set of size M = 2^n with mutually orthogonal U_i O U_i†. Entangled inputs are sampled from a set of Schmidt-rank-r states. N ∈ {1,…,16}, r ∈ {2^0,…,2^6}, and m ∈ {10, 100, 300, …, 5000, 20000}. Averaged prediction error is recorded over learning four different unitaries with 10 training datasets.

- Transition role of entangled data (Theorem 1): - Sufficient measurements: If r < m/(c1 2^n n), increasing Schmidt rank r decreases prediction error or reduces required N to achieve a target error. Extremes: r = 1 requires N ≈ 2^n c2 / n for zero averaged risk; r = 2^n needs N = 1, giving an exponential reduction in training data size. - Limited measurements: If r ≥ m/(c1 2^n n), increasing r can increase prediction error; entangled data may be harmful under low m due to reduced per-measurement information extraction. - Measurement resources: Beyond m ≥ r c1 2^n n, further increases in m do not improve error; at least r^2 c1 2^n n measurements are needed to fully exploit entangled data. - Query complexity: Minimum query complexity to achieve zero risk scales as Nm = O(4^n r c1 c2), matching optimal lower bounds for nonadaptive quantum state tomography in this setting and tightening prior results. - Generalized measurements (Theorem 2): The transition persists for arbitrary O and l-outcome POVMs. Increasing l can exponentially reduce the number of measurements needed; for constant l, query complexity scales like 2^n r log(|χ2(O)|), while for l = 2^n it scales like r log(|χ2(O)|). - Numerical evidence: For n = 4, - When m > 1000, prediction error decreases monotonically with increasing m and r (for N = 2 and N = 8). - For small m ≤ 100 (N = 8), error first decreases then increases with r, with critical points around r = 3 for m = 10 and r = 4 for m = 100, confirming the transition. Increasing N consistently lowers prediction error, aligning with the NFL perspective.

The findings answer the central question of how entanglement in training data affects learning quantum dynamics under finite measurements. They demonstrate a dual effect governed by measurement availability: with sufficient measurements, higher entanglement improves generalization or reduces sample complexity; with limited measurements, it can degrade performance due to reduced information per measurement. This clarifies when entangled data confer a practical quantum advantage and when they do not. The results guide QML protocol design: employ entangled data when measurement resources are ample and adapt measurement budgets to Schmidt rank; avoid highly entangled training data when measurement access is limited. The analysis also explains why entangled data can worsen query complexity in incoherent learning and shows that enlarging POVM outcome sets can mitigate measurement bottlenecks, potentially enabling advantages with fewer queries.

This work establishes a quantum no-free-lunch theorem for learning quantum dynamics with entangled data, revealing a transition role of entanglement controlled by the number of measurements. It proves that with sufficient measurements, greater entanglement reduces prediction error or training data requirements, while with limited measurements it can increase error. The study tightens lower bounds on query complexity, extends to arbitrary observables and POVMs, and provides numerical validation. These insights inform the design of QML protocols under realistic resource constraints. Future research directions include: (i) testing whether similar transition behavior holds for other QML tasks (e.g., learning unitaries or channels) under coherent and incoherent protocols; (ii) analyzing the joint use of entangled training states and entangled measurements (potentially with ancillas) to overcome information-extraction limits of projective measurements and further enhance quantum advantages.

- Theoretical results are average-case over Haar-distributed target unitaries and rely on small training error scaling ε ≈ 2^{-n}, which may limit direct applicability to structured or non-Haar targets. - Primary analysis focuses on incoherent learning with projective measurements and assumes all training inputs share the same Schmidt rank r, though an extension to arbitrary observables and POVMs is provided. - The lower bounds pertain to nonadaptive measurement settings; adaptive strategies might alter constants or regimes. - Numerical validation is limited to n = 4 qubits, discrete unitary sets of size 2^n with orthogonality under O, and specific ranges of N, r, and m. - Practical costs and noise in preparing high-Schmidt-rank entangled states and performing many measurements are not experimentally evaluated, which could affect real-world performance.