Related papers: Unweighted Gapped Clique Homology is $\mathsf{QMA}

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

URL: http://arxiv.org/abs/2608.02726v1
Date: Mon, 03 Aug 2026 18:00:02 GMT
Title: Unweighted Gapped Clique Homology is $\mathsf{QMA}_1$-complete
Abstract summary: We prove that $mathsfQMA$1g$ is $mathsfQMA$1g$ with the universal gate set $g=mathsfX,mathsf CX,mathsfCCX,Hotimes H$.<n>The block sizes are chosen so that symmetric averages reproduce the weighted Hodge metric.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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.

Related papers

Torsion detection in clique complexes is conditionally $QMA_1$-hard [0.0]
We show that detecting torsion in clique complexes is $NP$-hard, even under a constant gap promise.<n>Integral homology contains information inaccessible to the Laplacian spectrum.<n>We conclude that detecting torsion in clique complexes is $NP$-hard, even under a constant gap promise.
arXiv Detail & Related papers (2026-09-12T19:14:49Z)
A quantum oracle separation between QMA(2) and QMA [0.9068953081227296]
We find a quantum relative to which $mathsfQMA neq mathsfQMA(2)$.<n>We resolve the no-disentanglers conjecture of Watrous: for every $+1$, any $(, symmetric)$-disentangler requires input size exponential in the number of output qubits.
arXiv Detail & Related papers (2026-09-02T17:50:05Z)
Topology of the Set of Entangled State [0.0]
We show that $mathsf E$ is path-connected, and even simply connected except in the two-qubit case.<n>In this exceptional case $mathsf E$ turns out to be homotopy equivalent to the set of maximally entangled states.
arXiv Detail & Related papers (2026-07-20T16:04:26Z)
Non-Perturbative Closed Form for the Typical Bipartite Mutual Information of Haar-Random States [7.7281318046635015]
This quantity admits a single non-perturbative closed form.<n>$langle I(A:B)rangle = (d_A2-1)(d_B2-1),mathcalG(d_A,d_B,d_E)$, where $mathcalG$ is given by an explicit convergent integral over a Bose--Einstein kernel.
arXiv Detail & Related papers (2026-05-28T10:19:40Z)
Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability.<n>Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning.<n>We also highlight several open questions on quantitative sample complexity and evaluability.
arXiv Detail & Related papers (2026-05-13T15:41:30Z)
Spectral statistics and energy-gap scaling in $k-$local spin Hamiltonians [0.0]
We investigate the spectral properties of all-to-all interacting spin Hamiltonians acting on exactly $k$ spins.<n>For $mu = 0$, we demonstrate that the random matrix ensemble is determined by the parity of system size $L$ and locality $k$.<n>Our work introduces a semi-solvable model that captures universal features of random-matrix statistics, and spectral gap formation.
arXiv Detail & Related papers (2025-10-17T17:11:38Z)
Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
We study the complexity of a classic problem in computational topology, the homology problem. We find that the complexity is characterized by quantum complexity classes. Our results can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics.
arXiv Detail & Related papers (2023-11-28T21:15:30Z)
A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z)
Near-optimal fitting of ellipsoids to random points [68.12685213894112]
A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
arXiv Detail & Related papers (2022-08-19T18:00:34Z)
Monogamy of entanglement between cones [43.57338639836868]
We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones.<n>Our proof makes use of a new characterization of products of simplices up to affine equivalence.
arXiv Detail & Related papers (2022-06-23T16:23:59Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2021-10-21T18:43:00Z)
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
We study the asymmetric low-rank factorization problem: [mathbfU in mathbbRm min d, mathbfU$ and mathV$.
arXiv Detail & Related papers (2021-06-27T17:25:24Z)
Quantum double aspects of surface code models [77.34726150561087]
We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
arXiv Detail & Related papers (2021-06-25T17:03:38Z)
Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
arXiv Detail & Related papers (2021-04-26T15:03:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.