Rounding Almost Commuting Hamiltonians
This work provides the first efficient rounding method for almost commuting Hamiltonians, extending classical complexity results and algorithmic tools to a broader class of quantum many-body systems.
The authors develop an algorithmic rounding technique that maps any almost commuting 2-local qubit Hamiltonian to a nearby commuting one, with distance O(m ε^{1/6}), and show that δ-approximations to the ground energy for such Hamiltonians lie in NP when δ ≫ m ε^{1/6}. They also apply the method to Gibbs sampling and fast Hamiltonian simulation.
Commuting Hamiltonians lie at the boundary between classical constraint satisfaction and quantum many-body physics, exhibiting rich quantum structure while remaining more tractable than general noncommuting models. In contrast, physical Hamiltonians are rarely exactly commuting, which naturally motivates the study of almost commuting Hamiltonians. Despite their relevance, the implications of approximate commutation are only poorly understood. In this work, we show how to efficiently approximate any almost commuting $2$-local qubit Hamiltonian by a commuting one: we give a locality-preserving algorithmic rounding technique that maps any $2$-local Hamiltonian $H=\sum_{i=1}^m h_i$ with $\|[h_i,h_j]\| \leq ε$ to a nearby Hamiltonian $\hat{H}$ whose terms pair-wise commute, and which is within overall distance $\|H-\hat{H}\| = O(m\,ε^{1/6})$. As a consequence, we show that $δ$-approximations to the ground energy for $ε$-almost commuting $2$-local qubit Hamiltonians lie in $\mathsf{NP}$ when $δ\gg mε^{1/6}$, extending the classical containment well beyond the commuting setting. Finally, we present two applications of our rounding framework: Gibbs sampling and fast Hamiltonian simulation for almost commuting systems.