Generating large, nontrivial quantum chemistry test problems with known ground-state solutions remains a core challenge for benchmarking electronic structure methods. Inspired by planted-solution techniques from combinatorial optimization, we introduce four classes of Hamiltonians with embedded, retrievable ground states. These Hamiltonians mimic realistic electronic structure problems, support adjustable complexity, and are derived from reference systems. Crucially, their ground-state energies can be computed exactly, provided the construction parameters are known. To obscure this structure and control perceived complexity, we introduce techniques such as killer operators, balance operators, and random orbital rotations. We showcase this framework using examples based on homogeneous catalysts of industrial relevance and validate tunable difficulty through density matrix renormalization group convergence behavior. Beyond enabling scalable, ground-truth benchmark generation, our approach offers a controlled setting to explore the limitations of electronic structure methods and investigate how Hamiltonian structure influences ground state solution difficulty.
The local Hamiltonian problem consists of estimating the ground-state energy (given by the minimum eigenvalue) of a local quantum Hamiltonian. It can be considered as a quantum generalization of constraint satisfaction problems (CSPs) and has a key role in quantum complexity theory, being the first and most natural QMA-complete problem known. An interesting regime for the local Hamiltonian problem is that of extensive error, where one is interested in estimating the mean ground-state energy to constant accuracy. The problem is NP-hard by the PCP theorem, but whether it is QMA-hard is an important open question in quantum complexity theory. A positive solution would represent a quantum analogue of the PCP theorem. A key feature that distinguishes quantum Hamiltonians from classical CSPs is that the solutions may involve complicated entangled states. In this paper, we demonstrate several large classes of Hamiltonians for which product (i.e. unentangled) states can approximate the ground state energy to within a small extensive error.
Abstract Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is
QMA1 QMA 1 -complete (for
k≥3 k ≥ 3 , and where
QMA1 QMA 1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But whereas k-SAT has been well-studied for special tractable cases, as well as from a “parameterized complexity” perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state. Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or clauses. (2) We give a “parameterized algorithm” for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry.
The
k-local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchies provide systematic certificates for ground-state energies, but existing finite-convergence results give no quantitative guarantee on the accuracy of the low hierarchy levels accessible in computation. We prove explicit finite-level convergence rates for these hierarchies in the Pauli setting. For
k-local Hamiltonians whose Pauli expansion contains only even-weight terms, we show that both the NPA-type lower-bound hierarchy and the upper-bound hierarchy on the spectral minimum have error at most
C(k)ξd+1n,4/n, where
ξd+1n,4 is the smallest root of a Krawtchouk polynomial and
C(k) is independent of the number of qubits
n and the hierarchy level
d. General
k-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit while preserving the spectrum. The proof constructs almost-reproducing kernels for the Pauli algebra and relates their spectra to Krawtchouk polynomials, giving a noncommutative analogue of recent kernel-based convergence analyses for commutative polynomial optimization. These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.
We study the computational complexity of the Guided Local Hamiltonian problem: given a local Hamiltonian
H together with a classical description of a guiding state that has non-negligible overlap with the ground state of
H, estimate the ground-state energy within inverse-polynomial precision. This setting captures real-world scenarios in quantum chemistry and many-body physics, where trial states derived from classical heuristics can be used to guide quantum algorithms. We identify families of physically-motivated guiding states for which the computational hardness of ground-state energy estimation persists in the guided setting. Extending prior results for semi-classical subset states, we prove BQP-hardness for classes including fixed-weight states, matrix product states, Gaussian states, and Fendley states. Our hardness results are obtained via refined Feynman-Kitaev circuit-to-Hamiltonian constructions that explicitly expose the structural role of the guiding state in the reduction. Complementing these results, we give a constructive proof of BQP containment when the guiding state admits a polynomial-size classical description, establishing BQP-completeness for the canonical formulation of the problem. Our results show that quantum advantage persists for the newly introduced state classes, and classical methods also remain viable when said guiding states admit appropriate descriptions. Together, our results identify a Goldilocks zone of guiding states that are efficiently preparable, succinctly described, and sample-query accessible, within which quantum advantage for ground-state estimation can be meaningfully assessed. We additionally formalise the Guided Fermi-Hubbard Hamiltonian problem and prove BQP-completeness on 2D square and triangular lattices, both with and without magnetic fields, when provided with an appropriate fermionic guiding state.
A central question in quantum many-body physics is estimating the ground energy of a
k-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random
n-qubit Hamiltonian system defined as the sum of signed
k-local Pauli operators. In particular, we prove that for any constant
ℓ, there exists an efficiently computable length
nO(ℓ) certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an
ε-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on
k-XOR refutations to
k-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed
k-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1)
Ω(logn)-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to
Ω(n)-levels.