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 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-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-hard and belongs to 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-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 QMA1-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.
Clique Homology is QMA1-hard
Abstract Extracting meaningful information from large data sets is a challenging computational task. Here we show that the problem of extracting the “shape” of classical data, formalized in the Clique Homology Problem, is QMA1-hard, i.e., at least as hard as quantum k-SAT. For inputs satisfying a suitable promise the problem is contained in QMA, the class of problems that can be efficiently verified by a quantum computer. These results are ultimately rooted in the assertion, first noted by Witten, that the study of homology is equivalent to the study of quantum ground states of supersymmetric systems, a class of physical systems exhibiting a symmetry relating bosonic and fermionic states. We anticipate that the results reported here will serve as the starting point for investigating the possibility of quantum advantage in computational topology and classical data analysis using techniques from quantum many-body physics.
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.
Gapped Clique Homology on Weighted Graphs Is QMA1-Hard and Contained in QMA
Abstract. We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space [Formula: see text] and an integer [Formula: see text], decide if [Formula: see text] contains a [Formula: see text]-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics established by Witten (1982). We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every [Formula: see text]-clique in the graph to be a [Formula: see text]-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is [Formula: see text]-hard and contained in QMA. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory outlined by Forman (1994). Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work by Crichigno and Kohler (2022). Our result provides some suggestion that the quantum TDA algorithm due to Lloyd, Garnerone, and Zanardi (2016) cannot be dequantized, although proving this would require studying the complexity of a different problem related to the combinatorial Laplacian of clique complexes.
Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness & An Algorithm for Torsion Witness
Recent advances have revealed an interplay between quantum computing and topological data analysis (TDA). Most quantum TDA has focused on Betti numbers, which characterize the connectivity and ``holes'' of a dataset. Homology, however, contains additional information in the form of torsion: a nontrivial cycle can become trivial after being repeated finitely, revealing global constraints on how cycles combine and wrap around one another. Beyond applications in biomolecular studies, torsion appears in physical settings including homological quantum rotor codes, discrete charges, and gauge sectors. We study torsion from both classical and quantum perspectives. Given a graph G and its clique complex K=Cl(G), we first prove that, for fixed r and prime p, deciding whether Hr(K,Z) contains p-torsion is NP-hard. As a corollary, when a homological rotor code is specified by G, deciding whether the code has a finite-dimensional logical sector of a given order is NP-hard. We discuss related problems, including the Bockstein homomorphism, Smith normal form, lattice saturation, and cohomology. Second, for a finite set of primes P, we develop a quantum algorithm that serves as a one-sided torsion witness. For fixed r, it outputs WITNESS or INCONCLUSIVE, i.e. WITNESS certifies that either Hr(K,Z) or Hr−1(K,Z) contains p-torsion for some p∈P while INCONCLUSIVE makes no claim about its presence or absence. We identify a regime in which the algorithm achieves a near-quadratic quantum speedup over the corresponding classical algorithm under the same input model. Our NP-hardness result complements recent hardness results for estimating Betti numbers, adding a complexity-theoretic perspective to quantum TDA. Together, these results demonstrate that integral homology, beyond its Betti numbers, can be computationally challenging.
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.