Non-NP-Hardness of Translationally-Invariant Spin-Model Problems
arXiv:2111.10092
Abstract
Finding the ground state energy of the Heisenberg Hamiltonian is an important problem in the field of condensed matter physics. In some configurations, such as the antiferromagnetic translationally-invariant case on the 2D square lattice, its exact ground state energy is still unknown. We show that finding the ground state energy of the Heisenberg model cannot be an NP-Hard problem unless P=NP. We prove this result using a reduction to a sparse set and certain theorems from computational complexity theory. The result hints at the potential tractability of the problem and encourages further research towards a positive complexity result. In addition, we prove similar results for many similarly structured Hamiltonian problems, including certain forms of the Ising, t-J, and Fermi-Hubbard models.
References in corpus (5)
- Ising formulations of many NP problems
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- The antiferromagnetic spin-1/2 Heisenberg model on the square lattice in a magnetic field
- Merlin-Arthur Games and Stoquastic Complexity
- NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications