A Complete Proof of $\mathsf{QMA}_1$-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 $\mathsf{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 $\gamma(n)$, weighted gapped clique homology is $\mathsf{QMA}_1(\mathcal G)$-hard. The previously known $\mathsf{QMA}$-containment argument is logically independent of the gap and remains unaffected.

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

arXiv:2610.03584 [quant-ph]

(or arXiv:2610.03584v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.03584 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

certificates/CERTIFICATE_MANIFEST.md

certificates/PROVENANCE.md

certificates/README.md

certificates/RUN_ALL.sh

certificates/VERIFICATION_SUMMARY.txt

certificates/cert_c3_glued.py

certificates/cert_c4_coercivity.py

certificates/cert_c4_core.py

certificates/cert_geometry.py

certificates/compbasis.py

certificates/connecting_cert.py

certificates/diagnostics/c1_notebook_asis.py

certificates/fourq.py

certificates/fourq2.py

certificates/fourq_glued.py

certificates/gf2persist.py

certificates/gfp_persist.py

certificates/handedness_cert.py

certificates/logs/c0.log

certificates/logs/c2.log

certificates/logs/c3.log

certificates/logs/c4_coerc.log

certificates/logs/c4_core.log

certificates/logs/comp.log

certificates/logs/connecting.log

certificates/logs/diag_notebook_fourq.log

certificates/logs/geometry.log

certificates/logs/handedness.log

certificates/logs/interedges_resolution.log

certificates/pythag.py

certificates/pythag2.py

certificates/pythag_glued.py

certificates/resolve_interedges.py

certificates/run_c0_all.py

certificates/run_c2_all.py

certificates/run_c3_all.py

certificates/run_c4_coerc_all.py

certificates/run_c4_core_all.py

certificates/run_comp_all.py

certificates/run_geometry_all.py

certificates/simplicial.py

certificates/source_core_witnesses.json

certificates/sparserank.py

certificates/zlift.py

(40 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.