Efficient algorithms improve quantum ground energy estimation on large systems
Local Relaxation Hierarchies for Quantum Ground State Energies: Convergence Guarantees and Message Passing Algorithms
Distributed, Parallel, and Cluster Computing
Summary
Figuring out the lowest energy state of complex quantum systems helps scientists understand materials and particles, but the math is very tough. The authors created new ways to simplify these problems locally, allowing computers to calculate good estimates faster and for bigger systems. They proved their method works exactly in certain scenarios and gets better quickly in others. To do this, they designed fast algorithms that break the problem into smaller parts and share information efficiently. Their approach can handle large quantum models more effectively than older methods.
What this means in practice
- •For quantum software developers: Compute approximate ground state energies efficiently on large quantum system simulations using scalable local relaxation and message passing algorithms.
- •For classical hpc engineers: Implement parallel message passing methods to speed up convex relaxations for quantum physics problems on classical high-performance computing clusters.
Authors
Sheng-Ku Lin, Ricardo Rivera Cardoso, Roberto Bondesan
Abstract
Convex relaxation hierarchies provide lower bounds to the ground state energy of quantum many-body systems that can be computed in polynomial time on a classical computer, at any fixed hierarchy level. However, scaling these methods to large systems and accurate approximations remains challenging due to the computational cost of traditional solvers and the scarcity of efficiency guarantees. In this work, we develop local relaxation hierarchies and efficient, highly parallelisable message passing algorithms for estimating the relaxed ground state energies. We show that the first level of the hierarchy---based on local consistency of pairwise reduced density matrices---is exact for commuting Hamiltonians on trees. We further establish that another hierarchy, based on consistent intervals, converges exponentially fast in the interval size to the ground state energy for weak perturbations of separable Hamiltonians on a chain, thereby providing an efficient classical algorithm for these systems. Then, we introduce two variants of message passing algorithms that run in $\mathcal{O}(n/ε^2)$ and $\mathcal{O}(n/ε)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $ε$ is the precision for the relaxed ground state energy per site. This assumes that the optimal messages have $\mathcal{O}(1)$ norm---a condition we observe in practical settings in our experiments. These algorithms are based on the subgradient method and the Nesterov-type accelerated gradient descent method applied to an entropy-smoothed objective. Finally, we benchmark the message passing algorithms across different quantum Hamiltonians, lattice geometries, and relaxation levels, validating the theoretical predictions and their potential to surpass standard convex optimisation solvers for this problem. We release the resulting library at github.com/rick1924/gse-message-passing.