# On the Approximation Complexity of Matrix Product Operator (MPO) Born Machines

arXiv: https://arxiv.org/abs/2605.11471 · HTML: https://mlsanity.com/paper/2605.11471/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 34 references that are in the map.
- First posted on arXiv 12 May 2026.

## Builds on (most cited first, 25 of 25)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Tensorizing Neural Networks](https://mlsanity.com/paper/1509.06569/) (2015)
- [Unsupervised Generative Modeling Using Matrix Product States](https://mlsanity.com/paper/1709.01662/) (2017)
- [Tree Tensor Networks for Generative Modeling](https://mlsanity.com/paper/1901.02217/) (2019)
- [Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning](https://mlsanity.com/paper/1907.03741/) (2019)
- [Tensor Regression Networks](https://mlsanity.com/paper/1707.08308/) (2017)
- [Recent Advances for Quantum Neural Networks in Generative Learning](https://mlsanity.com/paper/2206.03066/) (2022)
- [Tensor-Train Density Estimation](https://mlsanity.com/paper/2108.00089/) (2021)
- [QuanTA: Efficient High-Rank Fine-Tuning of LLMs with Quantum-Informed Tensor Adaptation](https://mlsanity.com/paper/2406.00132/) (2024)
- [Generative Tensor Network Classification Model for Supervised Machine Learning](https://mlsanity.com/paper/1903.10742/) (2019)
- [Batch and match: black-box variational inference with a score-based divergence](https://mlsanity.com/paper/2402.14758/) (2024)
- [What is the Relationship between Tensor Factorizations and Circuits (and How Can We Exploit it)?](https://mlsanity.com/paper/2409.07953/) (2024)
- [Tensor networks for unsupervised machine learning](https://mlsanity.com/paper/2106.12974/) (2021)
- [Sum of Squares Circuits](https://mlsanity.com/paper/2408.11778/) (2024)
- [Variational Inference with Gaussian Score Matching](https://mlsanity.com/paper/2307.07849/) (2023)
- [Probabilistic Modeling with Matrix Product States](https://mlsanity.com/paper/1902.06888/) (2019)
- [EigenVI: score-based variational inference with orthogonal function expansions](https://mlsanity.com/paper/2410.24054/) (2024)
- [Generative Learning of Continuous Data by Tensor Networks](https://mlsanity.com/paper/2310.20498/) (2023)
- [Generative Modeling via Hierarchical Tensor Sketching](https://mlsanity.com/paper/2304.05305/) (2023)
- [TERM Model: Tensor Ring Mixture Model for Density Estimation](https://mlsanity.com/paper/2312.08075/) (2023)
- [Using matrix-product states for time-series machine learning](https://mlsanity.com/paper/2412.15826/) (2024)
- [Plastic tensor networks for interpretable generative modeling](https://mlsanity.com/paper/2504.06722/) (2025)
- [On the Hardness of Approximating Distributions with Tractable Probabilistic Models](https://mlsanity.com/paper/2506.01281/) (2025)
- [Regularized second-order optimization of tensor-network Born machines](https://mlsanity.com/paper/2501.18691/) (2025)

## Abstract (arXiv)

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.