A Complete Proof of 1-Hardness for Weighted Gapped Clique Homology

quant-ph, math.AT

Submitted: 2026-10-02

Updated: 2026-10-02

Comments: 75 pages, 5 figures. Ancillary file contains the exact finite certificates and verification code

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Sources

• Algorithms in Real Algebraic Geometry: A Survey
• Hamiltonian simulation with nearly optimal dependence on all parameters
• On the Rellich eigendecomposition of para-Hermitian matrices and the sign characteristics of $*$-palindromic matrix polynomials
• Efficient algorithm for a quantum analogue of 2-SAT
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Clique Homology is QMA1-hard
• Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• A quasiparticle-protected superconducting qubit
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians