On the NP-completeness of the Hartree-Fock method for translationally invariant systems
arXiv:1408.3459 · doi:10.1063/1.4903453
Abstract
The self-consistent field method utilized for solving the Hartree-Fock (HF) problem and the closely related Kohn-Sham problem, is typically thought of as one of the cheapest methods available to quantum chemists. This intuition has been developed from the numerous applications of the self-consistent field method to a large variety of molecular systems. However, as characterized by its worst-case behavior, the HF problem is NP-complete. In this work, we map out boundaries of the NP-completeness by investigating restricted instances of HF. We have constructed two new NP-complete variants of the problem. The first is a set of Hamiltonians whose translationally invariant Hartree-Fock solutions are trivial, but whose broken symmetry solutions are NP-complete. Second, we demonstrate how to embed instances of spin glasses into translationally invariant Hartree-Fock instances and provide a numerical example. These findings are the first steps towards understanding in which cases the self-consistent field method is computationally feasible and when it is not.
arXiv comment6 pages
References in corpus (8)
- Many-Body Physics with Ultracold Gases
- Ising formulations of many NP problems
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Hamiltonian complexity
- Computational Complexity in Electronic Structure
- Ground State Spin Logic
- Global Solutions of Hartree-Fock Theory and their Consequences for Strongly Correlated Quantum Systems
- Global solutions of restricted open-shell Hartree-Fock theory from semidefinite programming with applications to strongly correlated quantum systems