On the NPcompleteness of the HartreeFock method for translationally invariant systems
Abstract
The selfconsistent field method utilized for solving the HartreeFock (HF) problem and the closely related KohnSham 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 selfconsistent field method to a large variety of molecular systems. However, as characterized by its worstcase behavior, the HF problem is NPcomplete. In this work, we map out boundaries of the NPcompleteness by investigating restricted instances of HF. We have constructed two new NPcomplete variants of the problem. The first is a set of Hamiltonians whose translationally invariant HartreeFock solutions are trivial, but whose broken symmetry solutions are NPcomplete. Second, we demonstrate how to embed instances of spin glasses into translationally invariant HartreeFock instances and provide a numerical example. These findings are the first steps towards understanding in which cases the selfconsistent field method is computationally feasible and when it is not.
 Authors:

 Department of Computer Science, University College London, Gower Street, WC1E 6BT London (United Kingdom)
 Publication Date:
 OSTI Identifier:
 22413321
 Resource Type:
 Journal Article
 Journal Name:
 Journal of Chemical Physics
 Additional Journal Information:
 Journal Volume: 141; Journal Issue: 23; Other Information: (c) 2014 AIP Publishing LLC; Country of input: International Atomic Energy Agency (IAEA); Journal ID: ISSN 00219606
 Country of Publication:
 United States
 Language:
 English
 Subject:
 37 INORGANIC, ORGANIC, PHYSICAL AND ANALYTICAL CHEMISTRY; HAMILTONIANS; HARTREEFOCK METHOD; SELFCONSISTENT FIELD; SOLUTIONS; SPIN GLASS STATE
Citation Formats
Whitfield, James Daniel, Email: james.whitfield@univie.ac.at, Zimborás, Zoltán, and Department of Theoretical Physics, University of the Basque Country UPV/EHU, P.O. Box 644, E48080 Bilbao. On the NPcompleteness of the HartreeFock method for translationally invariant systems. United States: N. p., 2014.
Web. doi:10.1063/1.4903453.
Whitfield, James Daniel, Email: james.whitfield@univie.ac.at, Zimborás, Zoltán, & Department of Theoretical Physics, University of the Basque Country UPV/EHU, P.O. Box 644, E48080 Bilbao. On the NPcompleteness of the HartreeFock method for translationally invariant systems. United States. https://doi.org/10.1063/1.4903453
Whitfield, James Daniel, Email: james.whitfield@univie.ac.at, Zimborás, Zoltán, and Department of Theoretical Physics, University of the Basque Country UPV/EHU, P.O. Box 644, E48080 Bilbao. 2014.
"On the NPcompleteness of the HartreeFock method for translationally invariant systems". United States. https://doi.org/10.1063/1.4903453.
@article{osti_22413321,
title = {On the NPcompleteness of the HartreeFock method for translationally invariant systems},
author = {Whitfield, James Daniel, Email: james.whitfield@univie.ac.at and Zimborás, Zoltán and Department of Theoretical Physics, University of the Basque Country UPV/EHU, P.O. Box 644, E48080 Bilbao},
abstractNote = {The selfconsistent field method utilized for solving the HartreeFock (HF) problem and the closely related KohnSham 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 selfconsistent field method to a large variety of molecular systems. However, as characterized by its worstcase behavior, the HF problem is NPcomplete. In this work, we map out boundaries of the NPcompleteness by investigating restricted instances of HF. We have constructed two new NPcomplete variants of the problem. The first is a set of Hamiltonians whose translationally invariant HartreeFock solutions are trivial, but whose broken symmetry solutions are NPcomplete. Second, we demonstrate how to embed instances of spin glasses into translationally invariant HartreeFock instances and provide a numerical example. These findings are the first steps towards understanding in which cases the selfconsistent field method is computationally feasible and when it is not.},
doi = {10.1063/1.4903453},
url = {https://www.osti.gov/biblio/22413321},
journal = {Journal of Chemical Physics},
issn = {00219606},
number = 23,
volume = 141,
place = {United States},
year = {2014},
month = {12}
}