Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Continuum Coulomb hardness with binary nuclear charges

OpenAI

Published Oct 6, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.83295/by6b-7ewc

Related papers

QMA-hardness of continuum Coulomb energy with unit nuclear charges

OpenAI

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.

•Oct 6, 2026•0 citations

Quantum verification of full-continuum Coulomb energy with unit nuclei

Myeongjin Kang

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.

•Oct 25, 2026•0 citations

Intractability of Electronic Structure in a Fixed Basis

Bryan O’Gorman, Sandy Irani, James Daniel Whitfield +1 more

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.

arXiv:2103.08215•PRX Quantum•May 2, 2022•59 citations

A quantum annealing protocol to solve the nuclear shell model

Emanuele Costa, Axel Pérez-Obiol, J. Menéndez +3 more

The nuclear shell model accurately describes the structure and dynamics of atomic nuclei. However, the exponential scaling of the basis size with the number of degrees of freedom hampers a direct numerical solution for heavy nuclei. In this work, we present a quantum annealing protocol to obtain nuclear ground states. We propose a tailored driver Hamiltonian that preserves a large gap and validate our approach in a dozen nuclei with basis sizes up to 10^5 10 5 using classical simulations of the annealing evolution. We explore the relation between the spectral gap and the total time of the annealing protocol, assessing its accuracy by comparing the fidelity and energy relative error to classical benchmarks. While the nuclear Hamiltonian is non-local and thus challenging to implement in current setups, the estimated computational cost of our annealing protocol on quantum circuits is polynomial in the single-particle basis size, paving the way to study heavier nuclei.

arXiv:2411.06954•SciPost Physics•Aug 29, 2025•12 citations

Optimizing fermionic Hamiltonians with classical interactions

Maarten Stroeks, Barbara M. Terhal, Yaroslav Herasymenko

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.

arXiv:2510.02122•Oct 2, 2025•1 citation

XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games

Richard Cleve, Eric Culf, Aviv Taller

It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.

quant-pharXiv:2607.06876•Jul 9, 2026•0 citations
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.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.
The nuclear shell model accurately describes the structure and dynamics of atomic nuclei. However, the exponential scaling of the basis size with the number of degrees of freedom hampers a direct numerical solution for heavy nuclei. In this work, we present a quantum annealing protocol to obtain nuclear ground states. We propose a tailored driver Hamiltonian that preserves a large gap and validate our approach in a dozen nuclei with basis sizes up to 10^5 10 5 using classical simulations of the annealing evolution. We explore the relation between the spectral gap and the total time of the annealing protocol, assessing its accuracy by comparing the fidelity and energy relative error to classical benchmarks. While the nuclear Hamiltonian is non-local and thus challenging to implement in current setups, the estimated computational cost of our annealing protocol on quantum circuits is polynomial in the single-particle basis size, paving the way to study heavier nuclei.
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 that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. Håstad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.