Torsion detection in clique complexes is conditionally $QMA_1$-hard

• URL: http://arxiv.org/abs/2609.14110v1
• Date: Sat, 12 Sep 2026 19:14:49 GMT
• Title: Torsion detection in clique complexes is conditionally $QMA_1$-hard
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combinatorial Laplacian. Deciding whether a Betti number of a clique complex is nonzero is $QMA_1$-hard, and remains so under a spectral gap promise on vertex-weighted graphs. Integral homology, however, contains information inaccessible to the Laplacian spectrum. A new part that appears in integral homology is torsion: cycles that become boundaries only after being traversed several times, as in a projective plane or a Klein bottle. We ask how hard it is to detect torsion, and we answer with a simple reduction. We attach to an arbitrary clique complex a fixed $31$-vertex triangulation of the projective plane. The $k$th mod-$2$ Betti number of the input then reappears as $2$-torsion two degrees up, while all rational homology disappears and every combinatorial Laplacian acquires a constant spectral gap. We conclude that detecting torsion in clique complexes of unweighted graphs is $NP$-hard, even under a constant gap promise, and that it is $QMA_1$-hard if mod-$2$ clique homology is.

Related papers

• Unweighted Gapped Clique Homology is $\mathsf{QMA}_1$-complete [0.0]
  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.
  arXiv  Detail & Related papers  (2026-08-03T18:00:02Z)
• A Spectral Proof of the Hypergraph Moore Bound [46.26532142699448]
  We prove Feige's 2008 conjecture on the hypergraph Moore bound.<n>For every $kge3$ and every $1leellle n$, any $k$-uniform hypergraph on $n$ vertices with more than $C,nk/2/ellk/2-1$ hyperedges contains an even cover of size at most $A,elllog(en/ell)$.
  arXiv  Detail & Related papers  (2026-07-28T17:38:31Z)
• Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence [0.0]
  We give a quantum algorithm for identifying a hidden $d$-regular base graph $G$ on $n$ vertices from access to an obfuscated version of it.<n>Our algorithm is conceptually simple: a continuous-time walk on $G_rm spire$, followed by a single Hadamard test at a classically pret*$.
  arXiv  Detail & Related papers  (2026-05-11T20:44:32Z)
• Universal Complex Quantum-Like Bits from Hermitian Weighted Graphs [0.0]
  Block-coupled regular graphs can realize prescribed complex quantum-like bit states as exact synchronized eigenstates.<n>We show that exact discrete Hermitian realizations are dense in the synchronized pure-state space.
  arXiv  Detail & Related papers  (2026-04-27T03:09:53Z)
• Mesoscopic Fluctuations and Multifractality at and across Measurement-Induced Phase Transition [46.176861415532095]
  We explore statistical fluctuations over the ensemble of quantum trajectories in a model of two-dimensional free fermions.<n>Our results exhibit a remarkable analogy to Anderson localization, with $G_AB$ corresponding to two-terminal conductance.<n>Our findings lay the groundwork for mesoscopic theory of monitored systems, paving the way for various extensions.
  arXiv  Detail & Related papers  (2025-07-15T13:44:14Z)
• Geometric bound on structure factor [44.99833362998488]
  We show that a quadratic form of quantum geometric tensor in $k$-space sets a bound on the $q4$ term in the static structure factor $S(q)$ at small $vecq$.<n> Bands that saturate this bound satisfy a condition similar to Laplace's equation, leading us to refer to them as $textitharmonic bands$.
  arXiv  Detail & Related papers  (2024-12-03T18:30:36Z)
• 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)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  We introduce an observation-matrix-based framework for fully asynchronous online Federated Learning with adversaries. Our main result is that the proposed algorithm almost surely converges to the desired mean $mu.$ We derive this convergence using a novel differential-inclusion-based two-timescale analysis.
  arXiv  Detail & Related papers  (2023-04-04T04:32:29Z)
• Complete crystalline topological invariants from partial rotations in (2+1)D invertible fermionic states and Hofstadter's butterfly [6.846670002217106]
  We show how to extract many-body invariants $Theta_textopm$, where $texto$ is a high symmetry point, from partial rotations in (2+1)D invertible fermionic states. Our results apply in the presence of magnetic field and Chern number $C neq 0$, in contrast to previous work.
  arXiv  Detail & Related papers  (2023-03-29T18:00:00Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• 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)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.