Torsion detection in clique complexes is conditionally QMA 1-hard
quant-ph, cs.CC
Submitted: 2026-09-12
Updated: 2026-09-22
Terminology
Sources
- An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum Topological Data Analysis
- Complexity of Supersymmetric Systems and the Cohomology Problem
- Clique Homology is QMA1-hard
- Review of a Quantum Algorithm for Betti Numbers
- Provable quantum speedups for computing persistence in topological data analysis
- Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$
- Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
- A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits
- Topology and geometry of molecular conformational spaces and energy landscapes
- Defining and computing persistent Z-homology in the general case
- Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity