A Complete Proof of QMA1-Hardness for Weighted Gapped Clique Homology
Abstract
The computational complexity of simplicial homology has been studied since the question was raised by Kaibel and Pfetsch, and clique homology was later shown to be QMA1-hard by Crichigno and Kohler. King and Kohler subsequently introduced the weighted, spectrally gapped version considered here and developed a reduction intended to establish the same hardness result in this setting. We give a complete proof of the hard direction. The earlier King-Kohler argument contains a gap in the analysis of the nontrivially folded local gadgets, so the required topological and spectral properties have to be re-established on the clique complexes actually produced by the reduction. This is not a local repair of the published proof: the argument requires a new analysis of the local topology, the filtered cochain complexes, and the interaction of many overlapping gadgets. Our proof uses exact finite certificates for the local combinatorial data and relative homology to determine the effect of each gadget on the encoded qubit space. We then prove the finite-dimensional filtered-Hodge statement needed to recover the corresponding rank-one low-energy penalty and derive a quantitative global estimate that transfers the source-Hamiltonian promise gap to the final weighted Hodge Laplacian. Consequently, for fixed efficiently computable k(n) and inverse-polynomial γ(n), weighted gapped clique homology is QMA1(𝒢)-hard. The previously known QMA-containment argument is logically independent of the gap and remains unaffected.
Related
- Edge complexity of weighted graphs: involutory symmetries and NP-hardness
- Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times
- Weighted Homology and Cohomology of Weighted Polyhedra
- Weighted homogeneous surface singularities admitting rational homology disk smoothings
- Real polynomials with given multiplicities of real roots: Complete conjectural description of homology
BibTeX
@misc{barak2026complete,
title = {{A Complete Proof of $\mathsfQMA_1$-Hardness for Weighted Gapped Clique Homology}},
author = {Tal Barak},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03584},
eprint = {2610.03584},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03584},
}
RIS
TY - UNPB
TI - A Complete Proof of QMA_1-Hardness for Weighted Gapped Clique Homology
AU - Tal Barak
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03584
UR - https://arxiv.org/abs/2610.03584
AB - The computational complexity of simplicial homology has been studied since the question was raised by Kaibel and Pfetsch, and clique homology was later shown to be QMA_1-hard by Crichigno and Kohler. King and Kohler subsequently introduced the weighted, spectrally gapped version considered here and developed a reduction intended to establish the same hardness result in this setting. We give a complete proof of the hard direction. The earlier King-Kohler argument contains a gap in the analysis of the nontrivially folded local gadgets, so the required topological and spectral properties have to be re-established on the clique complexes actually produced by the reduction. This is not a local repair of the published proof: the argument requires a new analysis of the local topology, the filtered cochain complexes, and the interaction of many overlapping gadgets. Our proof uses exact finite certificates for the local combinatorial data and relative homology to determine the effect of each gadget on the encoded qubit space. We then prove the finite-dimensional filtered-Hodge statement needed to recover the corresponding rank-one low-energy penalty and derive a quantitative global estimate that transfers the source-Hamiltonian promise gap to the final weighted Hodge Laplacian. Consequently, for fixed efficiently computable k(n) and inverse-polynomial γ(n), weighted gapped clique homology is QMA_1(𝒢)-hard. The previously known QMA-containment argument is logically independent of the gap and remains unaffected.
ER -