Unweighted Gapped Clique Homology is $\mathsf{QMA}_1$-complete
Deciding whether the clique complex of a given graph has nontrivial homology in a given dimension, under vertex-product weighting and an inverse-polynomial spectral gap promise on the combinatorial Hodge Laplacian, is known to be $\mathsf{QMA}_1$-hard and contained in $\mathsf{QMA}$ by King and Kohler (FOCS 2024). The vertex weights are essential in the known proof, where they provide the scale separation needed for the spectral gap analysis. We prove that, when every vertex has weight one, the problem remains $\mathsf{QMA}_1^{g_2}$-hard and is contained in $\mathsf{QMA}_1^{g_2}$, where…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.02726
curl -X POST /api/v1/records/arxiv/2608.02726/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.02726/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'