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

Electronic Structure in a Fixed Basis is QMA-complete

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. 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.

arXiv:2103.08215•Mar 15, 2021•4 citations

Complexity Amplification from Compression in Quantum Random Access Optimization

Stuart Hadfield

Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli $X$, $Y$, and $Z$ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP $\cap$ StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.

quant-pharXiv:2609.07090•Sep 8, 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.

PRX Quantum•May 2, 2022•30 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•7 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. 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.
Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli XXX, YYY, and ZZZ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP ∩\cap∩ StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.
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.