Electronic Structure in a Fixed Basis is QMA-complete

Abstract

Finding the ground state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry. We prove that this electronic-structure problem, when restricted to a fixed single-particle basis and fixed number of electrons, is QMA-complete. Schuch and Verstraete have shown hardness for the electronic-structure problem with an additional site-specific external magnetic field, but without the restriction to a fixed basis. In their reduction, a local Hamiltonian on qubits is encoded in the site-specific magnetic field. In our reduction, the local Hamiltonian is encoded in the choice of spatial orbitals used to discretize the electronic-structure Hamiltonian. As a step in their proof, Schuch and Verstraete show a reduction from the antiferromagnetic Heisenberg Hamiltonian to the Fermi-Hubbard Hamiltonian. We combine this reduction with the fact that the antiferromagnetic Heisenberg Hamiltonian is QMA-hard to observe that the Fermi-Hubbard Hamiltonian on generic graphs is QMA-hard, even when all the hopping coefficients have the same sign. We then reduce from Fermi-Hubbard by showing that an instance of Fermi-Hubbard can be closely approximated by an instance of the Electronic-Structure Hamiltonian in a fixed basis. Finally, we show that estimating the energy of the lowest-energy Slater-determinant state (i.e., the Hartree-Fock state) is NP-complete for the Electronic-Structure Hamiltonian in a fixed basis.

37 pages

References in corpus (8)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Schrieffer-Wolff transformation for quantum many-body systems
• Quantum measurements and the Abelian Stabilizer Problem
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• N-representability is QMA-complete
• Interacting boson problems are QMA-hard
• QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge

Cited by in corpus (4)

• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• What the foundations of quantum computer science teach us about chemistry
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Efficient Quantum Cooling Algorithm for Fermionic Systems