  For quantum many-body systems in one dimension, computational complexity
theory reveals that the evaluation of ground-state energy remains elusive on
quantum computers, contrasting the existence of a classical algorithm for
temperatures higher than the inverse logarithm of the system size. This
highlights a qualitative difference between low- and high-temperature states in
terms of computational complexity. Here, we describe finite-temperature states
using the matrix product state formalism. Within the framework of random
samplings, we derive an analytical formula for the required number of samples,
which provides both quantitative and qualitative measures of computational
complexity. At high and low temperatures, its scaling behavior with system size
is linear and quadratic, respectively, demonstrating a distinct crossover
between these numerically difficult regimes of quantitative difference.
