arXiv：cs.LG· Chao Li, Zerui Tao, Yuchen Cong, Jian Xu, Qibin Zhao·· 13 小时前
MPO Born Machines 的近似复杂度研究：KL 误差下的 NP 难性与多项式键近似保证
On the Approximation Complexity of Matrix Product Operator (MPO) Born Machines
AI 导读
研究证明，构造多项式键 MPO-BM 以有界 KL 误差近似任意连续目标是 NP 难的。在正面结果上，满足对数 Sobolev 不等式且损失诱导哈密顿量局部、谱隙恒定的目标，允许具有可证明 KL 保证的多项式键 MPO-BM 近似；相同条件下，多项式数量的局部 score 查询足以保持 KL 保证。
正文
Abstract:Matrix product operator Born machines (MPO-BMs) are tractable tensor-network models for probabilistic modeling, yet their approximation capabilities remain poorly understood in theory. In this paper, we characterize these capabilities from both negative and positive perspectives. As a negative result, we prove that constructing a polynomial-bond MPO-BM approximation to an arbitrary continuous target with bounded KL error is NP-hard. On the positive side, for score-based variational inference, we prove that targets satisfying a log-Sobolev inequality admit polynomial-bond MPO-BM approximations with provable KL guarantees when the loss-induced Hamiltonian is local and has a constant spectral gap. Furthermore, under the same conditions, we construct local importance-sampling estimators and prove that polynomially many local score queries suffice to preserve the KL guarantees.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.11471 [cs.LG] |
| (or arXiv:2605.11471v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.11471 arXiv-issued DOI via DataCite |
Submission history
From: Chao Li [view email]
[v1]
Tue, 12 May 2026 03:38:49 UTC (4,254 KB)
[v2]
Fri, 9 Oct 2026 05:43:22 UTC (142 KB)
来源：arXiv：cs.LG · arxiv.org