We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), Ising spin glasses (p-spin model), and k-local constraint satisfaction problems (k-CSP). We show that either (a) the algorithm finds the optimal solution in time O*(2(0.5−c)n) for an n-independent constant c, a 2cn advantage over Grover’s algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a (1−η) approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of η. Additionally, we show that for a large fraction of random instances from the k-spin model and for any fully satisfiable or slightly frustrated k-CSP formula, statement (a) is the case. The algorithm and its analysis are largely inspired by Hastings’ short-path algorithm.

Tensor-network techniques have recently proven useful in machine learning, both as a tool for the formulation of new learning algorithms and for enhancing the mathematical understanding of existing methods. Inspired by these developments, and the natural correspondence between tensor networks and probabilistic graphical models, we provide a rigorous analysis of the expressive power of various tensor-network factorizations of discrete multivariate probability distributions. These factorizations include non-negative tensor-trains/MPS, which are in correspondence with hidden Markov models, and Born machines, which are naturally related to the probabilistic interpretation of quantum circuits. When used to model probability distributions, they exhibit tractable likelihoods and admit efficient learning algorithms. Interestingly, we prove that there exist probability distributions for which there are unbounded separations between the resource requirements of some of these tensor-network factorizations. Of particular interest, using complex instead of real tensors can lead to an arbitrarily large reduction in the number of parameters of the network. Additionally, we introduce locally purified states (LPS), a new factorization inspired by techniques for the simulation of quantum systems, with provably better expressive power than all other representations considered. The ramifications of this result are explored through numerical experiments.