We determine the computational complexity of deciding whether a supersymmetric quantum system on a one-dimensional chain has a zero-energy ground state. We prove $\mathrm{QMA}_1$-completeness for two input models, formulated in terms of Hermitian and nilpotent supercharges, respectively. In the Hermitian model, both the supercharge terms and the Hamiltonian have bounded range on the chain; in the nilpotent model, this geometric restriction applies only to the Hamiltonian. The hardness reduction from quantum satisfiability on a chain preserves exact zero energy and gives an inverse-polynomial ground-energy lower bound for negative instances. A common verification method establishes membership in $\mathrm{QMA}_1$ while allowing cancellations between supercharge terms.
Comments
39 pages. Corrected and simplified the proofs in Appendix B; added explanatory figures
Zero-Energy Problems for Supersymmetric Hamiltonians on a Chain Are QMA1-Complete
We determine the computational complexity of deciding whether a supersymmetric quantum system on a one-dimensional chain has a zero-energy ground state. We prove QMA1-completeness for two input models, formulated in terms of Hermitian and nilpotent supercharges, respectively. In the Hermitian model, both the supercharge terms and the Hamiltonian have bounded range on the chain; in the nilpotent model, this geometric restriction applies only to the Hamiltonian. The hardness reduction from quantum satisfiability on a chain preserves exact zero energy and gives an inverse-polynomial ground-energy lower bound for negative instances. A common verification method establishes membership in QMA1 while allowing cancellations between supercharge terms.
We consider the complexity of the local Hamiltonian problem in the context of fermionic Hamiltonians with N=2 supersymmetry and show that the problem remains QMA -complete. Our main motivation for studying this is the well-known fact that the ground state energy of a supersymmetric system is exactly zero if and only if a certain cohomology group is nontrivial. This opens the door to bringing the tools of Hamiltonian complexity to study the computational complexity of a large number of algorithmic problems that arise in homological algebra, including problems in algebraic topology, algebraic geometry, and group theory. We take the first steps in this direction by introducing the k -local Cohomology problem and showing that it is QMA1 -hard and, for a large class of instances, is contained in QMA . We then consider the complexity of estimating normalized Betti numbers and show that this problem is hard for the quantum complexity class DQC1 , and for a large class of instances is contained in BQP . In light of these results, we argue that it is natural to frame many of these homological problems in terms of finding ground states of supersymmetric fermionic systems. As an illustration of this perspective we discuss in some detail the model of Fendley, Schoutens, and de Boer consisting of hard-core fermions on a graph, whose ground state structure encodes l -dimensional holes in the independence complex of the graph. This offers a new perspective on existing quantum algorithms for topological data analysis and suggests new ones.
We discuss a supersymmetric generalization of the Sachdev-Ye-Kitaev (SYK) model. These are quantum mechanical models involving N Majorana fermions. The supercharge is given by a polynomial expression in terms of the Majorana fermions with random coefficients. The Hamiltonian is the square of the supercharge. The N=1 model with a single supercharge has unbroken supersymmetry at large N, but nonperturbatively spontaneously broken supersymmetry in the exact theory. We analyze the model by looking at the large N equation, and also by performing numerical computations for small values of N. We also compute the large N spectrum of ``singlet'' operators, where we find a structure qualitatively similar to the ordinary SYK model. We also discuss an N=2 version. In this case, the model preserves supersymmetry in the exact theory and we can compute a suitably weighted Witten index to count the number of ground states, which agrees with the large N computation of the entropy. In both cases, we discuss the supersymmetric generalizations of the Schwarzian action which give the dominant effects at low energies.
We study a 1D supersymmetric (SUSY) hard-core fermion model first proposed by Fendley, Schoutens, and de Boer [Phys. Rev. Lett. 90, 120402 (2003)]. We focus on the full Hilbert space instead of a restricted subspace. Exact diagonalization shows the degeneracy of zero-energy states scales exponentially with size of the system, with a recurrence relation between different system sizes. We solve the degeneracy problem by showing the ground states can be systematically constructed by inserting immobile walls of fermions into the chain. Mapping the counting problem to a combinatorial one and obtaining the exact generating function, we prove the recurrence relation on both open and periodic chains. We also provide an explicit mapping between ground states, giving a combinatorial explanation of the recurrence relation.
Despite immense progress in quantum Hamiltonian complexity in the past decade, little is known about the computational complexity of quantum physics at the thermodynamic limit. In fact, even defining the problem properly is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally-invariant (TI) Hamiltonian in the thermodynamic limit, to within a given precision; this precision (given by n the number of bits of the approximation) is the sole input to the problem. Understanding the complexity of this problem captures how difficult it is for a physicist to measure or compute another digit in the approximation of a physical quantity in the thermodynamic limit. We show that this problem is contained in FEXP QMA-EXP and is hard for FEXP NEXP . This means that the problem is doubly exponentially hard in the size of the input. As an ingredient in our construction, we study the problem of computing the ground energy of translationally invariant finite 1D chains. A single Hamiltonian term, which is a fixed parameter of the problem, is applied to every pair of particles in a finite chain. In the finite case, the length of the chain is the sole input to the problem and the task is to compute an approximation of the ground energy. No thresholds are provided as in the standard formulation of the local Hamiltonian problem. We show that this problem is contained in FP QMA-EXP and is hard for FP NEXP . Our techniques employ a circular clock structure in which the ground energy is calibrated by the length of the cycle. This requires more precise expressions for the ground energies of the resulting matrices than were required for previous QMA-completeness constructions and even exact analytical bounds for the infinite case which we derive using techniques from spectral graph theory. To our knowledge, this is the first use of the circuit-to-Hamiltonian construction that shows hardness for a function class.
We study the complexity of Local Hamiltonian problems under the restriction that every local term is an unweighted occurrence of the same fixed interaction. In the resulting Single-Interaction Hamiltonian (SIH) model, once the interaction is fixed, the Hamiltonian is specified entirely by its ordered interaction hypergraph.
Our main technical tool is an exact compiler that converts any fixed finite alphabet of local interactions into a single interaction. On a designated auxiliary subspace, the compiled Hamiltonian reproduces the source Hamiltonian exactly, while the complete spectrum below a chosen separation scale is preserved with multiplicity. Combined with a finite-alphabet normalization, this gives a universal polynomial-time reduction from k-Local Hamiltonian to SIH3k+3 up to a known global energy scale and inverse-polynomial approximation.
Sharper constructions give QMA-completeness of SIH3 and of geometrically local SIH8 with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH3 and QMA-completeness of 1-Pinned Stoq-SIH4. We also establish hardness results for uniformly system-size-dependent interactions and derive single-interaction formulations of the Hamiltonian quantum PCP conjecture, frustration-free, exponentially precise, and guided Local Hamiltonian problems. These results show that independently chosen local matrices and independently tunable coupling strengths are not necessary for a broad range of Hamiltonian-complexity phenomena.
We discuss a supersymmetric generalization of the Sachdev-Ye-Kitaev model. These are quantum mechanical models involving N Majorana fermions. The supercharge is given by a polynomial expression in terms of the Majorana fermions with random coefficients. The Hamiltonian is the square of the supercharge. The N=1 model with a single supercharge has unbroken supersymmetry at large N, but non-perturbatively spontaneously broken supersymmetry in the exact theory. We analyze the model by looking at the large N equation, and also by performing numerical computations for small values of N. We also compute the large N spectrum of "singlet" operators, where we find a structure qualitatively similar to the ordinary SYK model. We also discuss an N=2 version. In this case, the model preserves supersymmetry in the exact theory and we can compute a suitably weighted Witten index to count the number of ground states, which agrees with the large N computation of the entropy. In both cases, we discuss the supersymmetric generalizations of the Schwarzian action which give the dominant effects at low energies.