{"id":"630dacb3-1827-4c14-9421-aaf823da70ee","arxiv_id":"2412.05674","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Tensor-network machine learning models (MPS and PEPS) have average generalization risk lower bounded by explicit functions of training-set size and bond dimension, formalizing no-free-lunch limits for quantum-inspired learners.","lead":"This paper proves no-free-lunch (NFL) generalization bounds for machine learning models whose inputs are encoded as matrix product states (1D) and projected entangled-pair states (2D), showing average prediction risk stays high unless the training set is large. The result makes precise how a tensor network's bond dimension limits what quantum-inspired models can learn from data.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 1 and 2 are proven only for training subspaces that are tensor products of local site subspaces; their stated scope over arbitrary linearly independent training sets is unsupported.","rationale":"The reader's weakest-assumption analysis identifies the same load-bearing gap: the proofs of Theorems 1 and 2 are built on a local-product training-subspace ansatz (SI §B after Eq. (S34); SII §D after Eq. (S67)), while the theorem statements claim arbitrary linearly independent training sets. This is a real correctness risk for the central claim, because the overlap averages that define the risk are not obviously invariant under changing the training subspace, and the 2D proof further depends on a geometric amalgamation step that is asserted rather than proved. The numerical simulations in Fig. 2 do not resolve the gap: they show that average risks decrease with training-set size, but they never vary the training-subspace structure in a way that tests the claimed structure-independence. The empty- and full-training-set limits and the 1D transfer-matrix calculation are coherent for the restricted case, so this is a fixable gap rather than a demonstrated counterexample. The appropriate disposition is to keep the reader's CONDITIONAL verdict: the theorems should be restated for structured training sets, or a genuine invariance argument over training sets must be supplied. My stress-test pass does not change that verdict.","tokens_in":33004,"tokens_out":17296,"duration_ms":175435,"concrete_test":"Independently re-derive Eq. (S45) of SI §B with a generic rank-t_k projector P_S, e.g., P_S = U(I − Σ^{⊗k} ⊗ I)U† for a Haar-random U, in place of the special product projector. If tr[F({SWAP}) P_S ⊗ P_S] cannot be evaluated from the local transfer-matrix expressions (S41)–(S43), then Theorem 1 is established only for product training subspaces. For the 2D claim, run the same re-derivation on Z4 in SII §D without assuming the trained zone is an l×l square; if Eq. (S86) changes, Eq. (3) lacks support for arbitrary training sets.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the NFL lower bound depends only on the training-set size t_k, not on the structure of the training set. The proofs, however, only compute the average risk for a very special training subspace: SI §B after Eq. (S34) and SII §D after Eq. (S67) take M†PS = e^{iθ}(I − Σ^{⊗k} ⊗ I) + Σ^{⊗k} ⊗ Y, i.e., the training set spans the complement of a product of local |d⟩ states on k sites, with Y supported on the remaining sites. For a generic linear subspace of the same dimension t_k, the projector P_S cannot be written as I − Σ^{⊗k} ⊗ I, and the contraction of F({SWAP}) with W ⊗ W† no longer factorizes through the 1D transfer matrix or the 2D polyomino boundary count. No invariance argument is supplied showing that E_{M,S} is independent of the training subspace; in 2D the proof additionally assumes the k trained sites can be amalgamated into an l×l square so that ESSs are rooted only on two boundaries of length ≤ l (Eq. (S86)). For arbitrarily placed sites this boundary count is unjustified. The bounds as written therefore cover a restricted class of training sets, not the class stated in Theorems 1 and 2.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formulates no-free-lunch (NFL) bounds for tensor-network machine learning models that learn a target unitary from data encoded in random MPS and PEPS states. The main results are Theorem 1, a lower bound on the average risk E_{M,S}[R_M(P_S)] for MPS-encoded data depending on training-set size t_k, physical dimension d, and bond dimension D, and Theorem 2, an analogous bound for PEPS-encoded data that additionally involves a polyomino enumeration bound and a factor (1+c(0.7)^L). The 1D proof is presented through a transfer-matrix calculation of the second moment of random MPSs, and the 2D proof maps the corresponding second moment to a partition function whose configurations are controlled by directed polyominoes. Numerical simulations for small MPS systems (n=4,5) are reported as supporting the monotonic decrease of the risk with training-set size.","tokens_in":33315,"tokens_out":9906,"duration_ms":91728,"significance":"If the theorems as stated were established, this would be a valuable contribution: it would give the first rigorous NFL-type limitation for tensor-network learning models with an explicit dependence on the tensor-network bond and physical dimensions, and it would extend the analysis to 2D PEPS via a nontrivial polyomino counting argument. The 1D transfer-matrix derivation is explicit and algebraically consistent, and it reproduces the expected empty- and full-training-set limits. The numerical experiments, while modest in scale, support the qualitative trend of the analytical bounds. However, the proofs as written establish the bounds only for a highly structured family of training subspaces, not for the arbitrary linearly independent training sets named in the theorems; this gap is load-bearing for the paper's central claim.","major_comments":[{"comment":"The proofs of Theorems 1 and 2 evaluate the average risk only for the special learned unitary W = e^{iθ}(I_d^{⊗n} − Σ^{⊗k}⊗I_d^{⊗(n−k)}) + Σ^{⊗k}⊗Y, whose training subspace is the span of all computational-basis states in which not all of the first k sites are in |d⟩. This is a tensor-product-structured subspace, not a generic t_k-dimensional subspace. For an arbitrary linearly independent training set S, the correct form of W is e^{iθ}Π_S ⊕ Y in a basis adapted to S; in the computational basis Π_S is generally not a tensor product, so the transfer-matrix and polyomino factorizations of tr[F({SWAP}) W⊗W†] are not available. No invariance argument is given to show that the average over M and S is independent of the detailed structure of S, and no probability distribution over training sets is defined. Consequently Eqs. (2) and (3) are not established for arbitrary linearly independent training sets as stated.","section":"SI §B, Eq. (S34); SII §D, Eq. (S67)"},{"comment":"The 2D proof adds a geometric assumption that is absent from Theorem 2's statement: the k trained sites are amalgamated into an l×l square, and all nonzero ESSs outside the trained zone are assumed to be rooted on at most two boundaries of length l, leading to the factor (1+G(q_a,q_p^2))^{2l}. For an arbitrary placement of k trained sites on the L×L torus, the boundary of the trained region can have length far exceeding 2l, and ESSs can be rooted along several boundary segments or wind around the torus in ways not counted by Eq. (S86). The cycle-ESS bound in Eq. (S88) likewise depends on this specific geometry. Thus Theorem 2 is proven only for a restricted class of training-set geometries, not for the arbitrary training sets described in the theorem.","section":"SII §D, Eqs. (S86)–(S91)"},{"comment":"The decisive 2D estimates—the polyomino generating function G(q,p), the partition-function bound in Eq. (S63), and Corollary 1—are imported verbatim from Ref. [68] (described as 'Lemma 5 and Lemma 6 in Ref. [68]' and 'Theorem 1 in Ref. [68]'), while the main text says this paper introduces the combinatorial polyomino method. Because Theorem 2's proof rests on these imported bounds, the proof as presented is not self-contained, and the novelty attribution is inaccurate. The authors should include the necessary statements and proofs, or explicitly and accurately frame the contribution as applying the results of Ref. [68] to the NFL setting.","section":"SII B–C, Theorem 3, Corollary 1"}],"minor_comments":[{"comment":"The matrix Σ is used in the main-text proof sketch without definition; it is defined only in the Supplemental Material. Please define Σ = diag(0,0,...,1) in the main text.","section":"Main text, proof sketch after Theorem 1; SI Eq. (S34)"},{"comment":"The statement that the average risk is 'lower bounded by one' for the empty training set is imprecise, since the risk is at most one; the calculation in SI Eq. (S47) gives 1 − 1/d^n − ... ≈ 1. Rephrase as 'approaches one' in the relevant limit.","section":"Main text, paragraph after Eq. (2)"},{"comment":"There is a typo: 'uniatry embedded PEPS' should read 'unitary embedded PEPS'.","section":"SII, proof sketch of Theorem 2"},{"comment":"The symbol D is used both for the bond dimension of the tensor network and for the polyomino counts D_{m,n}; please rename one of these to avoid ambiguity.","section":"SII B and throughout"},{"comment":"The numerical experiments do not report the number of random target unitaries or training sets used for the averages, nor error bars; please specify these details so that the claimed monotonic decrease can be assessed quantitatively.","section":"Numerical Results and Fig. S5"}],"recommendation":"major_revision","confidential_remarks":"The paper's central dependence on Ref. [68], a same-group preprint, warrants editorial scrutiny regarding novelty disclosure and the reliability of the imported bounds. Theorems 1 and 2 as stated are broader than what the proofs actually establish; the authors should either extend the proofs to arbitrary linearly independent training sets or explicitly restrict the theorem statements to the product-structured training subspaces and geometries used in the derivations. The restricted results, if stated accurately, would still be a useful contribution after major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper claims NFL lower bounds on generalization risk for MPS- and PEPS-based learners, with explicit bond-dimension dependence. The 1D calculation is the real deal: the transfer-matrix reduction gives Eq. (2), the empty/full training-set limits behave, and the numerics agree qualitatively. The 2D bound is technically impressive but leans heavily on the authors' own unpublished polyomino machinery.\n\nThe soft spot is the gap between what Theorems 1 and 2 state and what the proofs actually cover. Both proofs assume the training subspace has a very special product form: the orthogonal complement of a single product state on k sites, so W = e^{iθ}(I − Σ^{⊗k}⊗I) + Σ^{⊗k}⊗Y factorizes through the local transfer matrix. The theorems are stated for arbitrary linearly independent training sets of that size. The average over M of the MPS-specific risk is not invariant under a global unitary change of basis for the training subspace—the MPS ensemble is only locally unitary invariant—so the move from one structured S to \"arbitrary S\" is not justified. Same issue in 2D, with an extra unproven amalgamation step that arranges the k trained sites into an l×l square for the boundary-root count.\n\nI don't think this is fatal. The restricted version—NFL for training sets that are complements of product states on a chosen set of sites—is a legitimate result and probably the intended one. Rewriting the theorems for that class, or supplying an invariance argument that actually goes through, would fix it. As written, the headline claim that the bound depends only on the size of the training set is not established for generic S.\n\nThe reliance on Ref. [68] for the core 2D lemmas is worth noting but not disqualifying; the lemmas are stated clearly, though their proofs live in an unpublished companion paper.\n\nWho should read it: people working on tensor-network ML theory and quantum NFL bounds. It deserves a serious referee, but the referee should push hard on the generality question. My recommendation: send it to review, with a request to either narrow the theorem statements or prove the missing invariance.","headline":"The 1D MPS bound is a clean, real result, but Theorems 1 and 2 overclaim: the proofs only handle product-structured training subspaces, not arbitrary linearly independent training sets.","tokens_in":33836,"tokens_out":5879,"would_cite":false,"duration_ms":59147,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","81P68","82B20","05A15"],"pacs":["03.67.-a","05.50.+q"],"model":"deepseek-v4-flash","headline":"Tensor-network machine learning models cannot escape a no-free-lunch limit: averaged over all target unitaries, their generalization risk is bounded below by a floor set by the training-set size and the network's bond and physical…","keywords":["no-free-lunch theorem","tensor network machine learning","matrix product states","projected entangled pair states","generalization risk","polyomino enumeration","Ising partition function","quantum machine learning"],"falsifier":"For a $2\\times 2$ PEPS with $d=D=2$, enumerate all $2^{L^2}=16$ spin configurations, evaluate the exact average risk from the partition-function sum, and compare it with the Theorem 2 lower bound for $k=1,2,3$; if the exact value falls below the bound, the theorem or one of its assumptions fails.","tokens_in":32724,"feed_emoji":"⚛️","tokens_out":9471,"duration_ms":85717,"temperature":0.7,"pith_summary":"The paper aims to prove no-free-lunch theorems for machine learning models built from tensor networks: averaged over every possible target unitary and every possible training set, the prediction error on unseen tensor-network-encoded inputs cannot be made small unless the training set is large. For matrix product states it proves an explicit lower bound on the average risk, and for two-dimensional projected entangled-pair states it proves the analogous bound. Both bounds depend on the training-set size, the physical dimension, and the bond dimension, so the inner structure of the tensor network itself sets the generalization floor. This matters because tensor-network models are widely proposed for quantum-inspired learning, and the results say their sample requirements are governed by a rigorous no-free-lunch limit, not just by practical training difficulties.","feed_headline":"Tensor-network learners hit a proven no-free-lunch wall","feed_subtitle":"New no-free-lunch bounds show average prediction error stays high until training sets fill the Hilbert space.","key_machinery":"The argument turns on writing the learned unitary as $W = M^\\dagger P_S = e^{i\\theta} I_{t_k} \\oplus Y$, so the training subspace is learned up to a phase and the complement is a free unitary, then expanding $W \\otimes W^\\dagger$ into five terms $Z_1,\\ldots,Z_5$. Each term is a second-moment integral over random local unitaries of the tensor network, and those integrals are evaluated by mapping them to partition functions of classical Ising models on the network lattice: a one-dimensional transfer matrix for MPS, and a two-dimensional Ising partition function for PEPS. The paper avoids solving the 2D Ising model directly by counting the contributing spin configurations as directed polyominoes, using the generating function $G(q,p)$ for directed polyominoes to bound the partition function by $1 + c(0.7)^L$. The local unitary 2-design property and norm concentration of random tensor-network states justify replacing the risk integral with this partition-function calculation.","core_discovery":"On its own terms, the paper establishes that learning an arbitrary unitary from tensor-network-encoded data is subject to a no-free-lunch limit. With the risk defined as the trace-norm distance between the target output $M|x\\rangle$ and the learned output $P_S|x\\rangle$ averaged over random local encoding unitaries, Theorem 1 lower-bounds the average risk for MPS inputs by the expression in Eq. (2), and Theorem 2 lower-bounds it for PEPS inputs by Eq. (3). The training sets are linearly independent and have size $t_k = d^n - d^{n-k}$ (MPS) or $t_k = d^{L^2} - d^{L^2-k}$ (PEPS); the bounds interpolate from near one for an empty training set to near zero only when the training set approaches the full Hilbert space. The central claim is therefore that no tensor-network learner can beat this dimension-dependent floor in the average case, and that the floor is set jointly by sample size and by the network's bond and physical dimensions.","pith_inferences":["A sympathetic reading suggests the bounds may carry over to other local tensor-network geometries whose second moments can be encoded as polyomino or similar lattice-animal counts, but the paper only proves the square-lattice PEPS case.","The results imply that entanglement in the encoded data does not rescue sample complexity in this averaged setting; the network's own dimensions enter the floor, unlike settings where entangled data can reduce error when measurements are plentiful.","Testing whether the bounds are tight, by exact enumeration on small PEPS lattices or larger MPS simulations with zero training error, would decide how much room remains for architecture-specific improvements."],"forward_implications":["An MPS- or PEPS-based learner with $t_k$ samples cannot push average risk below the stated floor; sample sizes approaching $d^n$ or $d^{L^2}$ are needed to make the average risk small.","The floor depends on bond dimension $D$ and physical dimension $d$, so the tensor network's internal structure, not merely the number of samples, controls generalization.","The same proof machinery yields no-free-lunch bounds for learning matrix product operators and for deep quantum neural networks that can be represented as MPSs.","In 2D, the polyomino counting method gives a rigorous bound without evaluating the 2D Ising partition function, so the approach transfers to other planar tensor-network geometries.","Empty training sets give average risk near one and complete training sets give average risk near zero, matching the classical no-free-lunch intuition that generalization is impossible without data."],"supporting_citations":[{"why":"Supplies the training-set averaging framework and the three cases of the learned-unitary decomposition used throughout the proofs.","marker":"[78]"},{"why":"Establishes that local random unitaries form approximate 2-designs and maps tensor-network second moments to Ising partition functions.","marker":"[67]"},{"why":"Provides norm concentration and random-MPS 2-moment and transfer-matrix techniques used in the 1D proof.","marker":"[88]"},{"why":"Supplies the polyomino machinery: torus-polyomino counting, Theorem 3, and Corollary 1 bounding the 2D partition function by $1+c(0.7)^L$.","marker":"[68]"},{"why":"Gives the exact generating function for directed polyominoes used to evaluate the 2D bound.","marker":"[102]"},{"why":"Supports identifying the risk function with generalization error for perfectly trained models.","marker":"[89]"},{"why":"Previous quantum no-free-lunch formulation that this work extends to tensor-network encodings.","marker":"[76]"}],"fun_headline_variants":["Tensor-network learning hits a proven no-free-lunch limit","No-free-lunch theorem proved for tensor-network models","Tensor-network learners face proven average-case limits","MPS and PEPS models can't beat no-free-lunch bound","Proof: tensor-network learners need huge training sets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that a perfectly trained model acts as a single global phase on the entire training subspace and as an arbitrary unitary on a complementary subspace that is a product of whole local sites (an approximate square block in 2D); if the training subspace has a generic shape, the site-by-site factorization of the second-moment calculation is not established, so the stated bounds are not proven.","fun_headline_variants_meta":{"raw":{"variants":["Tensor-network learning hits a proven no-free-lunch limit","No-free-lunch theorem proved for tensor-network models","Tensor-network learners face proven average-case limits","MPS and PEPS models can't beat no-free-lunch bound","Proof: tensor-network learners need huge training sets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000503,"raw_usage":{"total_tokens":2462,"prompt_tokens":958,"completion_tokens":1504,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":1426}},"tokens_in":574,"tokens_out":1504,"duration_ms":8753,"temperature":1.0,"reasoning_tokens":1426,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:29:41.600385+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a $2\\times 2$ PEPS with $d=D=2$, enumerate all $2^{L^2}=16$ spin configurations, evaluate the exact average risk from the partition-function sum, and compare it with the Theorem 2 lower bound for $k=1,2,3$; if the exact value falls below the bound, the theorem or one of its assumptions fails.","supporting_citations":[{"cited_title":"Sharma, M","cited_arxiv_id":null,"evidence_quote":"Supplies the training-set averaging framework and the three cases of the learned-unitary decomposition used throughout the proofs."},{"cited_title":"Haferkamp, C","cited_arxiv_id":null,"evidence_quote":"Provides norm concentration and random-MPS 2-moment and transfer-matrix techniques used in the 1D proof."},{"cited_title":"Theory on variational high-dimensional tensor networks","cited_arxiv_id":"2303.17452","evidence_quote":"Supplies the polyomino machinery: torus-polyomino counting, Theorem 3, and Corollary 1 bounding the 2D partition function by $1+c(0.7)^L$."},{"cited_title":"Bousquet-M´ elou, New enumerative results on two- dimensional directed animals, Discr","cited_arxiv_id":null,"evidence_quote":"Gives the exact generating function for directed polyominoes used to evaluate the 2D bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supports identifying the risk function with generalization error for perfectly trained models."}],"review_version":1}