On the NP-completeness of the Hartree-Fock method for translationally invariant systems

Whitfield, J. D. and Zimborás, Zoltán (2014) On the NP-completeness of the Hartree-Fock method for translationally invariant systems. JOURNAL OF CHEMICAL PHYSICS, 141 (23). ISSN 0021-9606

Preview

Text 1408.3459.pdf Download (286kB) | Preview

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.

Actions (login required)

Edit Item