Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

Abstract

In this paper, we present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least log(n) decays exponentially. We can improve the factor of log(n) to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems.

arXiv comment54 pages, 4 figures

References in corpus (19)

• String-net condensation: A physical mechanism for topological phases
• Undecidability of the Spectral Gap (short version)
• Solving Gapped Hamiltonians Locally
• The power of quantum systems on a line
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Approximating Gibbs states of local Hamiltonians efficiently with PEPS
• Locality of temperature
• Quantum Belief Propagation
• Rigorous RG algorithms and area laws for low energy eigenstates in 1D
• Quantum Approximate Markov Chains are Thermal
• Polynomial-time classical simulation of quantum ferromagnets
• Fisher zeros and correlation decay in the Ising model
• The Ising Partition Function: Zeros and Deterministic Approximation
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Monte Carlo simulation of stoquastic Hamiltonians
• On a conjecture of Sokal concerning roots of the independence polynomial
• Computing the partition function for cliques in a graph
• Markovian Matrix Product Density Operators : Efficient computation of global entropy
• Polynomial-time Classical Simulation for One-dimensional Quantum Gibbs States

Cited by in corpus (25)

• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Sample-efficient learning of quantum many-body systems
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Improved thermal area law and quasi-linear time algorithm for quantum Gibbs states
• On the complexity of quantum partition functions
• Exponential decay of mutual information for Gibbs states of local Hamiltonians
• Computing partition functions in the one clean qubit model
• The modified logarithmic Sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Learning quantum many-body systems from a few copies
• Limitations of optimization algorithms on noisy quantum devices
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Rapid thermalization of dissipative many-body dynamics of commuting Hamiltonians
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit
• Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature
• From decay of correlations to locality and stability of the Gibbs state
• Clustering theorem in 1D long-range interacting systems at arbitrary temperatures
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Efficient learning of ground & thermal states within phases of matter
• Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits
• High-temperature partition functions and classical simulatability of long-range quantum systems
• Stability of thermal equilibrium in long-range quantum systems
• Classical Simulation of High Temperature Quantum Ising Models
• Short proof of a spectral Chernoff bound for local Hamiltonians