Abstract
Matrix product states (MPS) are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state $\ket{\psi_{1, \ldots, n}} \in \mathbb{C}^{d_1} \otimes \cdots \otimes \mathbb{C}^{d_n}$ comprised of $n$ qudits is said to be an MPS of bond dimension $r$ if the reduced density matrix $\psi_{1, \ldots, k}$ has rank at most $r$ for each $k \in {1, \ldots, n}$. When $r = 1$, this corresponds to the set of product states, i.e. states of the form $\ket{\psi_1} \otimes \cdots \otimes \ket{\psi_n}$, which possess no entanglement. For larger values of $r$, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement.
Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. In this work, we study the problem of testing whether an unknown state $\ket{\psi}$ is an MPS in the property testing model. In this model, one is given $m$ identical copies of $\ket{\psi}$, and the goal is to determine whether $\ket{\psi}$ is an MPS of bond dimension $r$ or whether $\ket{\psi}$ is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro (FOCS, 2010), and a key ingredient in their proof that $\mathsf{QMA}(2) = \mathsf{QMA}(k)$ for $k \geq 2$. We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems in (Harrow and Montanaro, 2010) and (Montanaro and de Wolf, 2016). For the case of $r \geq 2$, we give an algorithm for testing whether $\ket{\psi}$ is an MPS of bond dimension $r$ using $m = O(n r^2)$ copies, and we show that $\Omega(n^{1/2})$ copies are necessary for this task. This lower bound shows that a dependence on the number of qudits $n$ is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.
