  The reconstruction of quantum states from experimental measurements, often
achieved using quantum state tomography (QST), is crucial for the verification
and benchmarking of quantum devices. However, performing QST for a generic
unstructured quantum state requires an enormous number of state copies that
grows \emph{exponentially} with the number of individual quanta in the system,
even for the most optimal measurement settings. Fortunately, many physical
quantum states, such as states generated by noisy, intermediate-scale quantum
computers, are usually structured. In one dimension, such states are expected
to be well approximated by matrix product operators (MPOs) with a finite
matrix/bond dimension independent of the number of qubits, therefore enabling
efficient state representation. Nevertheless, it is still unclear whether
efficient QST can be performed for these states in general.
  In this paper, we attempt to bridge this gap and establish theoretical
guarantees for the stable recovery of MPOs using tools from compressive sensing
and the theory of empirical processes. We begin by studying two types of random
measurement settings: Gaussian measurements and Haar random rank-one Positive
Operator Valued Measures (POVMs). We show that the information contained in an
MPO with a finite bond dimension can be preserved using a number of random
measurements that depends only \emph{linearly} on the number of qubits,
assuming no statistical error of the measurements. We then study MPO-based QST
with physical quantum measurements through Haar random rank-one POVMs that can
be implemented on quantum computers. We prove that only a \emph{polynomial}
number of state copies in the number of qubits is required to guarantee bounded
recovery error of an MPO state.
