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

arXiv:2608.29333

Zero-Energy Problems for Supersymmetric Hamiltonians on a Chain Are $\mathrm{QMA}_1$-Complete

Yibin Wang

quant-phSubmitted Aug 29, 2026• Announced Sep 1, 2026• 0 citations• Revised Sep 1, 2026 (v2)
v1 · Aug 29, 2026v2 · Sep 1, 2026v3 · Oct 2, 2026
arXivHTMLPDF

Abstract

We study exact zero modes of supersymmetric quantum systems whose interactions are arranged on a one-dimensional chain. For Hermitian supercharges, deciding whether a zero mode exists is $\mathrm{QMA}_1$-complete, and the hard instances are geometrically local on a chain. We also classify an explicitly encoded nilpotent $\mathcal{N}=2$ formulation: its exact-zero problem is $\mathrm{QMA}_1$-complete, including the restriction in which the associated Hamiltonian is local on a chain. Both classifications use a verification theorem for simultaneous sparse linear constraints and the same one-dimensional frustration-free Hamiltonian construction. The construction gives an explicit inverse-polynomial lower bound on the ground energy of every reduced NO instance, separating it from zero.

Related papers

Complexity of Supersymmetric Systems and the Cohomology Problem

Chris Cade, P. Marcos Crichigno

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.

arXiv:2107.00011•Quantum•Apr 30, 2024•17 citations

The Fermionic Cohomology Problem on the Full Fock Space Is $\mathrm{QMA}_1$-Complete

Yibin Wang

Fermionic cohomology detects zero-energy states of supersymmetric Hamiltonians. Previous work showed that deciding nonzero cohomology in an input-specified particle-number sector is $\mathrm{QMA}_1$-hard and belongs to $\mathrm{QMA}$. We study total cohomology on the unrestricted full Fock space, where a NO instance must exclude zero-energy states in every sector and in their superpositions. We prove that this global problem is $\mathrm{QMA}_1$-complete. The input differential is an operator that raises fermion number by one and squares to zero on the full Fock space. It is given as an exact list of local fermionic monomials, each involving at most $41$ modes. The reduction encodes each data site by one fermion in a block of modes. Every sector violating this occupation rule has energy at least one. An exact quantum verifier accepts a suitable witness with certainty on every YES instance, establishing containment with perfect completeness. We also prove $\mathrm{QMA}_1$-completeness for the problem in an input-specified particle-number sector. Its hard instances use $30$-mode terms and admit a one-dimensional block-chain realization.

quant-pharXiv:2609.00694•Sep 2, 2026•0 citations

Supersymmetric Sachdev-Ye-Kitaev models

Wenbo Fu, Davide Gaiotto A, JUAN M. MALDACENA +1 more

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 $\mathcal{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 $\mathcal{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.

Physical review. D/Physical review. D.•Jan 13, 2017•334 citations

Hamiltonian Complexity in the Thermodynamic Limit

Dorit Aharonov, Sandy Irani

Despite progress in quantum Hamiltonian complexity, little is known about the computational complexity of quantum physics at the thermodynamic limit. Even defining the problem is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally invariant Hamiltonian in the thermodynamic limit, to within a given precision; the number of bits $n$ for the precision is the sole input to the problem. The complexity of this problem captures how difficult it is for the 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 $\mbox{FEXP}^{\mbox{QMA-EXP}}$ and is hard for $\mbox{FEXP}^{\mbox{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. 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 $\mbox{FP}^{\mbox{QMA-EXP}}$ and is hard for $\mbox{FP}^{\mbox{NEXP}}$. Our techniques employ a circular clock in which the ground energy is calibrated by the length of the cycle. This requires more precise expressions for the ground states of the resulting matrices than was 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 which shows hardness for a function class.

arXiv:2107.06201•Jul 13, 2021•2 citations

The Complexity of Single-Interaction Hamiltonians

Elad Hecker

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 SIH$_{3k+3}$ up to a known global energy scale and inverse-polynomial approximation. Sharper constructions give QMA-completeness of SIH$_3$ and of geometrically local SIH$_8$ with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH$_3$ and QMA-completeness of 1-Pinned Stoq-SIH$_4$. 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.

quant-pharXiv:2609.39592•Oct 1, 2026•0 citations

Local symmetries and extensive ground-state degeneracy of a 1D supersymmetric fermionic chain

Shuyu Zhang, Hiroki Sukeno, Kazuki Ikeda +1 more

We study a $1$D 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.

arXiv:2412.17208•Dec 23, 2024•0 citations
Zero-Energy Problems for Supersymmetric Hamiltonians on a Chain Are QMA1\mathrm{QMA}_1QMA1​-Complete
We study exact zero modes of supersymmetric quantum systems whose interactions are arranged on a one-dimensional chain. For Hermitian supercharges, deciding whether a zero mode exists is QMA1\mathrm{QMA}_1QMA1​-complete, and the hard instances are geometrically local on a chain. We also classify an explicitly encoded nilpotent N=2\mathcal{N}=2N=2 formulation: its exact-zero problem is QMA1\mathrm{QMA}_1QMA1​-complete, including the restriction in which the associated Hamiltonian is local on a chain. Both classifications use a verification theorem for simultaneous sparse linear constraints and the same one-dimensional frustration-free Hamiltonian construction. The construction gives an explicit inverse-polynomial lower bound on the ground energy of every reduced NO instance, separating it from zero.
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.
The Fermionic Cohomology Problem on the Full Fock Space Is QMA1\mathrm{QMA}_1QMA1​-Complete
Fermionic cohomology detects zero-energy states of supersymmetric Hamiltonians. Previous work showed that deciding nonzero cohomology in an input-specified particle-number sector is QMA1\mathrm{QMA}_1QMA1​-hard and belongs to QMA\mathrm{QMA}QMA. We study total cohomology on the unrestricted full Fock space, where a NO instance must exclude zero-energy states in every sector and in their superpositions. We prove that this global problem is QMA1\mathrm{QMA}_1QMA1​-complete. The input differential is an operator that raises fermion number by one and squares to zero on the full Fock space. It is given as an exact list of local fermionic monomials, each involving at most 414141 modes. The reduction encodes each data site by one fermion in a block of modes. Every sector violating this occupation rule has energy at least one. An exact quantum verifier accepts a suitable witness with certainty on every YES instance, establishing containment with perfect completeness. We also prove QMA1\mathrm{QMA}_1QMA1​-completeness for the problem in an input-specified particle-number sector. Its hard instances use 303030-mode terms and admit a one-dimensional block-chain realization.
We discuss a supersymmetric generalization of the Sachdev-Ye-Kitaev (SYK) model. These are quantum mechanical models involving NNN 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\mathcal{N}=1N=1 model with a single supercharge has unbroken supersymmetry at large NNN, but nonperturbatively spontaneously broken supersymmetry in the exact theory. We analyze the model by looking at the large NNN equation, and also by performing numerical computations for small values of NNN. We also compute the large NNN spectrum of ``singlet'' operators, where we find a structure qualitatively similar to the ordinary SYK model. We also discuss an N=2\mathcal{N}=2N=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 NNN computation of the entropy. In both cases, we discuss the supersymmetric generalizations of the Schwarzian action which give the dominant effects at low energies.
Despite progress in quantum Hamiltonian complexity, little is known about the computational complexity of quantum physics at the thermodynamic limit. Even defining the problem is not straight forward. We study the complexity of estimating the ground energy of a fixed, translationally invariant Hamiltonian in the thermodynamic limit, to within a given precision; the number of bits nnn for the precision is the sole input to the problem. The complexity of this problem captures how difficult it is for the 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 $\mbox{FEXP}^{\mbox{QMA-EXP}}$ and is hard for $\mbox{FEXP}^{\mbox{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. 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 $\mbox{FP}^{\mbox{QMA-EXP}}$ and is hard for $\mbox{FP}^{\mbox{NEXP}}$. Our techniques employ a circular clock in which the ground energy is calibrated by the length of the cycle. This requires more precise expressions for the ground states of the resulting matrices than was 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 which 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 kkk-Local Hamiltonian to SIH3k+3_{3k+3}3k+3​ up to a known global energy scale and inverse-polynomial approximation. Sharper constructions give QMA-completeness of SIH3_33​ and of geometrically local SIH8_88​ with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH3_33​ and QMA-completeness of 1-Pinned Stoq-SIH4_44​. 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 study a 111D 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.