Many Body Theory 3

Abstract: We prove that to learn an $N$-qubit state with $\varepsilon$ error in trace distance, $\Tilde{\Theta}(\frac{10^N}{\eps^2})$ copies are necessary and sufficient using Pauli measurements, where $\Tilde{\Theta}$ hides a $\sqrt{N}$ factor. The lower bound holds under adaptivity. Thus, we nearly settle the worst-case copy complexity of Pauli tomography, which has been a long-standing problem. Our main technical contribution is a novel lower bound framework for adaptive single-copy state tomography with measurement constraints. Our method allows measurement-dependent hard instances for tighter lower bounds, and characterizes the hardness of learning using the \emph{measurement information channel}. The power of our framework extends beyond Pauli measurements: We prove that Pauli measurements are near-optimal among single-qubit measurements, and further prove tight lower bounds for adaptive $k$-outcome measurements.

Abstract: Thermalization is the process through which a physical system evolves toward a state of thermal equilibrium. Determining whether or not a physical system will thermalize from an initial state has been a key question in condensed matter physics. Closely related questions are determining whether observables in these systems relax to stationary values, and what those values are. Using tools from computational complexity theory, we demonstrate that given a Hamiltonian on a finite-sized system, determining whether or not it thermalizes or relaxes to a given stationary value is computationally intractable, even for a quantum computer. In particular, we show that the problem of determining whether an observable of a finite-sized quantum system relaxes to a given value is PSPACE-complete, and so no efficient algorithm for determining the value is expected to exist. Further, we show the existence of Hamiltonians for which the problem of determining whether the system thermalizes to the Gibbs expectation value is PSPACE-complete. We also show that the related problem of determining whether the system thermalizes to the microcanonical expectation value is contained in PSPACE and is PSPACE-hard under quantum polynomial time reductions. In light of recent results demonstrating undecidability of thermalization in the thermodynamic limit, our work shows that the intractability of the problem is due to inherent difficulties in many-body physics rather than particularities of infinite systems.

Abstract: A central challenge of quantum physics is to understand the structural properties of many-body systems, both in equilibrium and out of equilibrium. For classical systems, we have a unified perspective which connects structural properties of systems at thermal equilibrium to the Markov chain dynamics which mix to them. We lack such a perspective for quantum systems: many of the most fundamental ideas of the modern classical theory are notably absent from our quantum toolkit. We develop a theory which brings the broad scope and flexibility of the classical theory to quantum Gibbs states at high temperature. At its core is a natural quantum analogue of Dobrushin’s condition; whenever this condition holds, a concise path-coupling argument proves rapid mixing for the corresponding Markovian evolution. The same machinery bridges dynamic and structural properties: rapid mixing yields exponential decay of CMI without restrictions on the size of the probed subsystems, resolving a central question in the theory of open quantum systems. Our key technical insight is an optimal transport viewpoint which couples the quantum dynamics to a linear differential equation, enabling precise control over how local deviations from equilibrium propagate to distant sites.