title: On the NP-completeness of the Hartree-Fock method for translationally invariant systems.
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.
authors.affiliation: Vienna Center for Quantum Science and Technology, Department of Physics, University of Vienna, Boltzmanngasse 5, Vienna, Austria.
authors.forename: James Daniel
authors.initials: JD
authors.lastname: Whitfield
authors.affiliation: Department of Computer Science, University College London, Gower Street, WC1E 6BT London, United Kingdom.
authors.forename: Zoltán
authors.initials: Z
authors.lastname: Zimborás