arXiv preprint ·
A Complete Proof of $\mathsf{QMA}_1$-Hardness for Weighted Gapped Clique Homology
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $γ(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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Cups and Gates II: Operads, twists, and addressable intra-code gates
A differentiability framework for zigzag persistent homology via linear interpolation
The sublevel Flood bifiltration: towards scalable 2-parameter persistent homology
T-ARC: Topology-Aware Randomized Clustering via Distributionally Robust Stochastic Block Models
Constructive Bounds for the Topological Expressivity of Neural Networks
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.