  Devising schemes for testing the amount of entanglement in quantum systems
has played a crucial role in quantum computing and information theory. Here, we
study the problem of testing whether an unknown state $|\psi\rangle$ is a
matrix product state (MPS) in the property testing model. MPS are a class of
physically-relevant quantum states which arise in the study of quantum
many-body systems. A quantum state $|\psi_{1,...,n}\rangle$ comprised of $n$
qudits is said to be an MPS of bond dimension $r$ if the reduced density matrix
$\psi_{1,...,k}$ has rank $r$ for each $k \in \{1,...,n\}$. When $r=1$, this
corresponds to the set of product states. For larger values of $r$, this yields
a more expressive class of quantum states, which are allowed to possess limited
amounts of entanglement. In the property testing model, one is given $m$
identical copies of $|\psi\rangle$, and the goal is to determine whether
$|\psi\rangle$ is an MPS of bond dimension $r$ or whether $|\psi\rangle$ 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 of Harrow and Montanaro (FOCS 2010) and
Montanaro and de Wolf (2016). For the case of $r\geq 2$, we give an efficient
algorithm for testing whether $|\psi\rangle$ is an MPS of bond dimension $r$
using $m = O(n r^2)$ copies, independent of the dimensions of the qudits, 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.
