  We consider the problem of approximating ground states of one-dimensional
quantum systems within the two most common variational ansatzes, namely the
mean field ansatz and Matrix Product States. We show that both for mean field
and for Matrix Product States of fixed bond dimension, the optimal solutions
can be found in a way which is provably efficient (i.e., scales polynomially).
This implies that the corresponding variational methods can be in principle
recast in a way which scales provably polynomially. Moreover, our findings
imply that ground states of one-dimensional commuting Hamiltonians can be found
efficiently.
