Unweighted Gapped Clique Homology is $\mathsf{QMA}_1$-complete

arXiv:2608.02726v1 Announce Type: new Abstract: 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 $\mathsf{QMA}_1^{g_2}$ is $\mathsf{QMA}_1$ with the universal gate set $g_2=\{\mathsf{X},\mathsf{CX},\mathsf{CCX},H\otimes H\}$. The construction replaces weight by expansion: each vertex of the weighted complex is blown up into a clique whose size encodes its weight. The block sizes are chosen so that symmetric averages reproduce the weighted Hodge metric. The symmetric sector therefore carries the weighted Laplacian up to a common scalar factor, while a local averaging argument gives a uniform lower bound on the orthogonal complement to the symmetric sector. Hence the weighted gap analysis transfers to an unweighted clique complex without introducing either additional low-energy states or spurious homology. Containment in $\mathsf{QMA}_1^{g_2}$ follows from Rudolph's exact linear combination of unitaries simulation of sparse integer clique Laplacians. The result shows that the gap promise, rather than vertex weighting, is the source of the complexity of gapped clique homology.

Abstract: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 $\mathsf{QMA}_1^{g_2}$ is $\mathsf{QMA}_1$ with the universal gate set $g_2=\{\mathsf{X},\mathsf{CX},\mathsf{CCX},H\otimes H\}$. The construction replaces weight by expansion: each vertex of the weighted complex is blown up into a clique whose size encodes its weight. The block sizes are chosen so that symmetric averages reproduce the weighted Hodge metric. The symmetric sector therefore carries the weighted Laplacian up to a common scalar factor, while a local averaging argument gives a uniform lower bound on the orthogonal complement to the symmetric sector. Hence the weighted gap analysis transfers to an unweighted clique complex without introducing either additional low-energy states or spurious homology. Containment in $\mathsf{QMA}_1^{g_2}$ follows from Rudolph's exact linear combination of unitaries simulation of sparse integer clique Laplacians. The result shows that the gap promise, rather than vertex weighting, is the source of the complexity of gapped clique homology.

arXiv:2608.02726 [quant-ph]

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

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

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.

analiza aiqbench

Unweighted Gapped Clique Homology is $\mathsf{QMA}_1$-complete

Subiecte conexe