Skip to content
Preprint

A Complete Proof of $\mathsf{QMA}_1$-Hardness for Weighted Gapped Clique Homology

Oct 2026 · 0 citations
Physics Mathematics

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.

View source

Similar papers

Preprint Nov 2026

A proof of the Theta conjecture

We prove the touching refinement of the Theta conjecture of Interdonato and Iraci, giving a formula for $\Theta_{e_\ell}\Theta_{e_k}\nabla E_{d,j}$ as a weighted sum over parking functions with decorated rises and valleys and touch number $j$. Summing over $j$ gives the Theta conjecture. As corollaries, we prove the va...

Hao-Jun Bai, Feng-Ren Gu, Zhuo-Wei Lin et al. · 0 citations
Preprint Sep 2026

Myopic Tutte polynomials and Khovanov homology in $\mathbb{R}P^3$

We present a"myopic"Tutte polynomial for graphs on $\mathbb{R}P^2$ which takes only nullhomologous spanning subgraphs as input. It recovers the generalized Krushkal polynomial and Drobotukhina's analogue of the Jones polynomial for alternating, nullhomologous links in $\mathbb{R}P^3$. We use this myopic Tutte polynomia...

Keegan Boyle, Dean Spyropoulos · 0 citations
Preprint Oct 2026

Vanishing near the virtual cohomological dimension of $\mathrm{SL}_n(\mathbb Z)$

We prove the Church--Farb--Putman conjecture that \[ H^{N_n-i}(\mathrm{SL}_n(\mathbb Z);\mathbb Q)=0, \qquad N_n=\binom n2,\quad n\ge2,\quad 0\le i<n-1. \] The proof relies on Franke's filtration of the weighted automorphic cochain complex, developed in his proof of Borel's conjecture. We treat trivial and nontrivial c...

Tai-Wang Deng · 0 citations
Preprint Nov 2026

The Gorsky-Oblomkov-Rasmussen conjecture over $\mathbb{Q}$

We prove a generation theorem for the homology of certain Koszul complexes which naturally arise as the $E^1$ pages of the stable Rasmussen spectral sequence of torus links. Combining this theorem with recent work of Ballinger, Gorsky, Hogancamp, and Wang, we compute the stable Khovanov-Rozansky $\mathfrak{gl}_N$ homol...

Qiu-Yu Ren, Hong-Jian Yang · 0 citations
Preprint Nov 2026

The geometric case of the Erd\H{o}s Similarity Conjecture. A human exposition of the OpenAI proof

For a fixed $q\in(0,1)$, can a set of positive Lebesgue measure avoid every translated and dilated copy of $\{q^n:n\ge1\}$? OpenAI's release of October 6, 2026 shows that it can, with a compact subset of $[0,1]$ whose measure is arbitrarily close to one. We give a detailed exposition of the proof, using only finite pro...

A. Iosevich, A. Yavicoli · 1 citation
Preprint Nov 2026

A proof of the constant-width numerical range conjecture

We prove the conjecture of Chien, Nakazato, and Meng that the numerical range of a finite complex matrix has constant width $d$ if and only if it is a closed disk of radius $d/2$, with a singleton allowed when $d=0$. For $d>0$, the characteristic polynomial of the associated Hermitian pencil and its translate by $d$ ha...

Mu-Yan Jiang · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.