On the Approximation Complexity of Matrix Product Operator (MPO) Born Machines
This work investigates how well Matrix Product Operator Born Machines (MPO-BMs) can approximate probability distributions. It shows that in the worst case, approximating a target distribution is computationally hard (NP-hard). However, MPO-BMs become efficient approximators when certain conditions like locality and a spectral gap are met, allowing for polynomial bond dimension and query complexity.