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:2609.00694

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

Yibin Wang

quant-phSubmitted Sep 1, 2026• Announced Sep 2, 2026• 0 citations
v1 · Sep 1, 2026v2 · Sep 8, 2026
arXivHTMLPDF

Abstract

Fermionic cohomology characterizes the zero-energy states of the supersymmetric Hamiltonian associated with a fermionic differential. Previous work showed that the problem restricted to a particle-number sector specified with the input is $\mathrm{QMA}_1$-hard and belongs to $\mathrm{QMA}$. We study the global problem, in which no sector is specified and cohomology may occur anywhere in the full Fock space. This formulation directly matches the whole-space ground-state question: a specified-degree NO instance may still have zero-energy states in another sector, whereas the global NO promise excludes them across all sectors and their superpositions. We prove that this full-Fock problem is $\mathrm{QMA}_1$-complete for differentials given as exact lists of local monomials, even when each monomial acts on at most $41$ modes. As a companion result, we prove $\mathrm{QMA}_1$-completeness for the specified-degree problem with $30$-mode terms whose hard instances admit a one-dimensional block-chain realization.

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

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

Yibin Wang

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.

quant-pharXiv:2608.29333•Sep 1, 2026•0 citations

Finite Fermionic Universality from Token Graphs

Monte Brocco

Finite Fermionic Universality from Token Graphs establishes a general finite-dimensional operator-algebra theorem for many-fermion systems. Given a finite graph G on m one-particle modes, the induced support on the k-fermion sector ∧ᵏℂᵐ is exactly the k-token graph Fₖ(G). With a diagonal occupation-label operator Dₖ having simple spectrum and a Hermitian transfer operator A_G,k supported on the token graph, the generated C*-algebra is C*(Dₖ, A_G,k) ≅ ⨁_{C ∈ π₀(Fₖ(G))} M_|C|(ℂ). In particular, when G is connected, C*(Dₖ + iA_G,k) = M_{(m choose k)}(ℂ), for every 1 ≤ k ≤ m − 1. Thus a single explicitly constructed nonnormal operator generates the complete matrix algebra on every fixed-particle-number fermionic sector. The paper proves the token-graph lift and connectivity theorem from first principles, constructs matrix units explicitly along token-graph paths, derives exact synthesis depth from graph distance, gives edge-count and diameter formulas, and classifies the superselection structure that appears when the one-particle graph is disconnected. The analysis also extends to full fermionic Fock space. For an explicit hopping-plus-pairing construction, fermion parity is the surviving superselection label and the generated algebra is M_{2ᵐ⁻¹}(ℂ) ⊕ M_{2ᵐ⁻¹}(ℂ), with commutant span{I, P}. The result is independent of superconducting phenomenology. It is a finite operator-algebra and graph-theoretic universality theorem and does not, by itself, assert a superconducting phase, select a material Hamiltonian, or establish a thermodynamic limit.

•Sep 5, 2026•0 citations

Nonadditivity in fermionic quantum Shannon theory

Farzin Salek, Amir-Reza Negari, Graeme Smith +2 more

We study collective state preparation and channel encoding in fermionic systems under parity superselection and composition governed by the canonical anticommutation relations. For a two-mode Gaussian state $τ$, we obtain the exact entanglement of formation, $E_{\mathrm F}^{\mathrm{phys}}(τ^{\otimes m})=\lceil m/2\rceil\log2$ for every $m\geq1$. Two copies have the same formation value as one, violating additivity and strong superadditivity, while regularization halves the single-copy value. For an associated Gaussian channel, we determine the minimum output entropy and Holevo information at every blocklength and prove nonadditivity of both. Together, these results give exact answers to the fermionic counterparts of the four additivity questions associated with Shor and Hastings. One physical use carries no classical information, whereas two uses transmit one bit perfectly. The unassisted classical and zero-error classical capacities both equal one half bit per mode. A sharp finite-block bound gives a strong converse: the decoding success probability vanishes at every rate above capacity. These optimizations cover all physical pure-state decompositions and channel inputs, with Gaussian ensembles and classical codes attaining the optima. The formation and minimum output entropy formulas hold for every Rényi order $α\in(0,\infty]$. We also determine the unassisted quantum and zero-error quantum capacities, both equal to one half logical qubit per mode, and prove a strong converse: entanglement fidelity vanishes at every rate above capacity. For a noisy Gaussian family, we determine the one- and two-copy formation values and prove strict nonadditivity at full rank. For $τ$, Bell violation under local parity-preserving measurements first appears at three copies.

quant-pharXiv:2610.06758•Oct 6, 2026•0 citations

Complexity of Fermionic 2-SAT

Maarten Stroeks, Barbara M. Terhal

We introduce the fermionic satisfiability problem, Fermionic k -SAT: this is the problem of deciding whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on n fermionic modes, where each fermionic projector involves at most k fermionic modes. We prove that this problem can be solved efficiently classically for k = 2 . In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA 1 -hard.

arXiv:2412.06383•Quantum•Oct 31, 2025•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
The Fermionic Cohomology Problem on the Full Fock Space Is QMA1\mathrm{QMA}_1QMA1​-Complete
Fermionic cohomology characterizes the zero-energy states of the supersymmetric Hamiltonian associated with a fermionic differential. Previous work showed that the problem restricted to a particle-number sector specified with the input is QMA1\mathrm{QMA}_1QMA1​-hard and belongs to QMA\mathrm{QMA}QMA. We study the global problem, in which no sector is specified and cohomology may occur anywhere in the full Fock space. This formulation directly matches the whole-space ground-state question: a specified-degree NO instance may still have zero-energy states in another sector, whereas the global NO promise excludes them across all sectors and their superpositions. We prove that this full-Fock problem is QMA1\mathrm{QMA}_1QMA1​-complete for differentials given as exact lists of local monomials, even when each monomial acts on at most 414141 modes. As a companion result, we prove QMA1\mathrm{QMA}_1QMA1​-completeness for the specified-degree problem with 303030-mode terms whose hard instances admit a one-dimensional block-chain realization.
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.
Zero-Energy Problems for Supersymmetric Hamiltonians on a Chain Are QMA1\mathrm{QMA}_1QMA1​-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\mathrm{QMA}_1QMA1​-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\mathrm{QMA}_1QMA1​ while allowing cancellations between supercharge terms.
Finite Fermionic Universality from Token Graphs establishes a general finite-dimensional operator-algebra theorem for many-fermion systems. Given a finite graph G on m one-particle modes, the induced support on the k-fermion sector ∧ᵏℂᵐ is exactly the k-token graph Fₖ(G). With a diagonal occupation-label operator Dₖ having simple spectrum and a Hermitian transfer operator A_G,k supported on the token graph, the generated C*-algebra is C*(Dₖ, A_G,k) ≅ ⨁_{C ∈ π₀(Fₖ(G))} M_|C|(ℂ). In particular, when G is connected, C*(Dₖ + iA_G,k) = M_{(m choose k)}(ℂ), for every 1 ≤ k ≤ m − 1. Thus a single explicitly constructed nonnormal operator generates the complete matrix algebra on every fixed-particle-number fermionic sector. The paper proves the token-graph lift and connectivity theorem from first principles, constructs matrix units explicitly along token-graph paths, derives exact synthesis depth from graph distance, gives edge-count and diameter formulas, and classifies the superselection structure that appears when the one-particle graph is disconnected. The analysis also extends to full fermionic Fock space. For an explicit hopping-plus-pairing construction, fermion parity is the surviving superselection label and the generated algebra is M_{2ᵐ⁻¹}(ℂ) ⊕ M_{2ᵐ⁻¹}(ℂ), with commutant span{I, P}. The result is independent of superconducting phenomenology. It is a finite operator-algebra and graph-theoretic universality theorem and does not, by itself, assert a superconducting phase, select a material Hamiltonian, or establish a thermodynamic limit.
We study collective state preparation and channel encoding in fermionic systems under parity superselection and composition governed by the canonical anticommutation relations. For a two-mode Gaussian state τττ, we obtain the exact entanglement of formation, EFphys(τ⊗m)=⌈m/2⌉log⁡2E_{\mathrm F}^{\mathrm{phys}}(τ^{\otimes m})=\lceil m/2\rceil\log2EFphys​(τ⊗m)=⌈m/2⌉log2 for every m≥1m\geq1m≥1. Two copies have the same formation value as one, violating additivity and strong superadditivity, while regularization halves the single-copy value. For an associated Gaussian channel, we determine the minimum output entropy and Holevo information at every blocklength and prove nonadditivity of both. Together, these results give exact answers to the fermionic counterparts of the four additivity questions associated with Shor and Hastings. One physical use carries no classical information, whereas two uses transmit one bit perfectly. The unassisted classical and zero-error classical capacities both equal one half bit per mode. A sharp finite-block bound gives a strong converse: the decoding success probability vanishes at every rate above capacity. These optimizations cover all physical pure-state decompositions and channel inputs, with Gaussian ensembles and classical codes attaining the optima. The formation and minimum output entropy formulas hold for every Rényi order α∈(0,∞]α\in(0,\infty]α∈(0,∞]. We also determine the unassisted quantum and zero-error quantum capacities, both equal to one half logical qubit per mode, and prove a strong converse: entanglement fidelity vanishes at every rate above capacity. For a noisy Gaussian family, we determine the one- and two-copy formation values and prove strict nonadditivity at full rank. For τττ, Bell violation under local parity-preserving measurements first appears at three copies.
We introduce the fermionic satisfiability problem, Fermionic k -SAT: this is the problem of deciding whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on n fermionic modes, where each fermionic projector involves at most k fermionic modes. We prove that this problem can be solved efficiently classically for k = 2 . In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA 1 -hard.
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.