Testing matrix product states

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 |ψ 1,...,n ∈ C d1 ⊗ • • • ⊗ C dn comprised of n qudits is said to be an MPS of bond dimension r if the reduced density matrix ψ 1,...,k has rank r for each k ∈ 1, . . . , n. When r = 1, this corresponds to the set of product states, i.e. states of the form |ψ 1 ⊗ • • • ⊗ |ψ 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 |ψ is an MPS in the property testing model. In this model, one is given m identical copies of |ψ , and the goal is to determine whether |ψ is an MPS of bond dimension r or whether |ψ 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 [HM13], and a key ingredient in their proof that QMA(2) = QMA(k) for k ≥ 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 [HM13] and [MdW13]. For the case of r ≥ 2, we give an efficient algorithm for testing whether |ψ is an MPS of bond dimension r using m = O(nr 2 ) copies, independent of the dimensions of the qudits, and we show that Ω(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.