Speaker
Description
Computational complexity of physical states is a critical topic because it relates to the preparation on classical or quantum computers, as well as in real experiments. From the perspective of computational complexity theory, thermal and ground states of one-dimensional systems are well-understood. There exists an efficient classical algorithm for calculating thermal states at temperatures with $\beta = \mathcal{o}(\log N)$, where $N$ is the system size [1]. On the other hand, estimating the ground state energy is generally challenging even for quantum computers [2]. This difference between thermal and ground states has not been thoroughly explored.
In this work, we derive an exact analytical form for the required number of samples in random samplings based on the matrix product state. Previous research has shown that the required number of samples is characterized by the normalized fluctuation of the partition function, denoted as $\delta z^2$ [3]. We find a qualitative change in $\delta z^2$ with temperature; at high temperatures $\beta \lesssim \beta_c$, $\delta z^2$ scales linearly with $N$, and at low temperatures $\beta \gtrsim \beta_c$, $\delta z^2$ scales as $N^2$. Here, the crossover temperature $\beta_c$ depends on the system size as
\begin{equation}
\beta_c \simeq \frac{1}{\Delta E} \log N
\end{equation}
where $\Delta E$ is the spectral gap. This result bridges the difference in computational complexity between thermal and ground states.
[1] T. Kuwahara, A. M. Alhambra, and A. Anshu, Phys. Rev. X 11, 011047
(2021).
[2] S. Hallgren, D. Nagaj, and S. Narayanaswami, Quantum Info. Comput.
13, 721–750 (2013).
[3] A. Iwaki and C. Hotta, Phys. Rev. B 106, 094409 (2022).
