We prove that approximating the electronic ground-energy infimum for clamped unit-charge nuclei is QMA-hard on the full spinful fermionic continuum space. A deterministic classical polynomial-time reduction produces polynomially many nuclei at distinct rational positions and polynomially many electrons, with polynomial rational bit lengths and threshold separation at least one. No orbital basis, magnetic field, or additional external potential is supplied, and no binding assumption is imposed.
We prove that approximating the electronic ground-energy infimum for clamped unit-charge nuclei is QMA-hard on the full spinful fermionic continuum space. A deterministic classical polynomial-time reduction produces polynomially many nuclei at distinct rational positions and polynomially many electrons, with polynomial rational bit lengths and threshold separation at least one. No orbital basis, magnetic field, or additional external potential is supplied, and no binding assumption is imposed.
We prove that approximating the electronic Coulomb spectral infimum in three-dimensional space is QMA-hard when positive integer nuclear charges are encoded in binary. The nuclei have distinct rational positions, the electron number is unary, and the energy is minimized over all antisymmetric continuum states and spin sectors. A deterministic classical polynomial-time reduction produces instances with threshold separation at least one. The nuclear charges may be exponentially large, but every output has polynomial bit length.
We prove uniform QMA membership for the spectral-infimum decision problem for the full spinful antisymmetric Coulomb Hamiltonian with unit nuclei, distinct rational nuclear positions, unary electron number and inverse-polynomial promise gap. Nuclear repulsion is omitted. Positions and thresholds use binary rational encoding; the result assumes neither binding nor a spectral gap, geometric separation, bounded physical diameter, a selected finite basis, a fixed spin sector or an efficiently prepared low-energy state. The proof combines quantitative localization including escaped electrons, Hardy-controlled Coulomb caps, a finite kinetic cutoff, exact shifted sampling with L2 error control, and a polynomial-size verifier on arbitrary witness states. Together with the hardness theorem of the pinned source manuscript, this gives QMA completeness for the same problem. Classical sector localization, finite-basis electronic complexity, smooth-box discretization and earlier real-space simulation estimates are credited. The accompanying Lean support proves selected finite sampling, representation-average and scalar error interfaces; it does not formalize the full continuum or quantum-complexity theorem. No extension to exponentially large binary nuclear charges or worldwide priority claim is made. AI-assisted preprint by Myeongjin Kang, with no affiliation. Internal AI review is not external journal peer review or worldwide-priority certification. Identified OpenAI source inputs at revision fd4aeeb2ee4fc729c18d98444fed42fd0529eeeb are stipulated true. Lean verifies scoped supporting results only, not the full theorem. Original prose: CC BY 4.0; original code and Lean: MIT; third-party rights preserved. See the supporting archive for precise assumptions, coverage, provenance and corrections.
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.
Finding the ground-state energy of electrons subject to an external electric field is a fundamental problem in computational chemistry.While the theory of QMA-completeness has been instrumental in understanding the complexity of finding ground states in many-body quantum systems, prior to this work it has been unknown whether or not the special form of the Hamiltonian for the electronic structure of molecules can be exploited to find ground states efficiently or whether the problem remains hard for this special case.We prove that the electronic-structure problem, when restricted to a fixed single-particle basis and a fixed number of electrons, is QMA-complete.In our proof, the local Hamiltonian is encoded in the choice of spatial orbitals used to discretize the electronic-structure Hamiltonian.In contrast, Schuch and Verstraete have proved hardness for the electronic-structure problem with an additional site-specific external magnetic field, but without the restriction to a fixed basis, by encoding a local Hamiltonian on qubits in the site-specific magnetic field.We also show that estimation of the energy of the lowest-energy Slater-determinant state (i.e., the Hartree-Fock state) is nondeterministic polynomial time (NP)-complete for the electronic-structure Hamiltonian in a fixed basis.
We consider the optimization problem (ground energy search) for fermionic Hamiltonians with classical interactions. This QMA-hard problem is motivated by the Coulomb electron-electron interaction being diagonal in the position basis, a fundamental fact that underpins electronic-structure Hamiltonians in quantum chemistry and condensed matter. We prove that fermionic Gaussian states achieve an approximation ratio of at least 1/3 for such Hamiltonians, independent of sparsity. This shows that classical interactions are sufficient to prevent the vanishing Gaussian approximation ratio observed in SYK-type models. We also give efficient semi-definite programming algorithms for Gaussian approximations to several families of traceless and positive-semidefinite classically interacting Hamiltonians, with the ability to enforce a fixed particle number. The technical core of our results is the concept of a Gaussian blend, a construction for Gaussian states via mixtures of covariance matrices.
It is well-known in physics that the limit of large quantum spin S should be understood as a semiclassical limit. This raises the question of whether such emergent classicality facilitates the approximation of computationally hard quantum optimization problems, such as the local Hamiltonian problem. We demonstrate this explicitly for spin-S generalizations of Quantum Max-Cut (QMaxCutS), equivalent to the problem of finding the ground state energy of an arbitrary spin-S quantum Heisenberg antiferromagnet (QHAS). We prove that approximating the value of QHAS to inverse polynomial accuracy is QMA-complete for all S, extending previous results for S=1/2. We also present two distinct families of classical approximation algorithms for QMaxCutS based on rounding the output of a semidefinite program to a product of Bloch coherent states. The approximation ratios for both our proposed algorithms strictly increase with S and converge to the Briët-Oliveira-Vallentin approximation ratio αBOV≈0.956 from below as S→∞.