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

Autor(en)

James Daniel Whitfield, Zoltan Zimboras

Abstrakt

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

Organisation(en)

Quantenoptik, Quantennanophysik und Quanteninformation

Externe Organisation(en)

University of the Basque Country, University College London

Journal

Journal of Chemical Physics

Band

141

Anzahl der Seiten

6

ISSN

0021-9606

DOI

https://doi.org/10.1063/1.4903453

Publikationsdatum

12-2014

Peer-reviewed

Ja

ÖFOS 2012

103025 Quantenmechanik, 103006 Chemische Physik

Schlagwörter

ASJC Scopus Sachgebiete

Allgemeine Physik und Astronomie, Physical and Theoretical Chemistry

Link zum Portal

https://ucrisportal.univie.ac.at/de/publications/0eddb5bb-47fa-4d31-84cc-261b4a059386