3 papers
quant-ph2026
Unweighted Gapped Clique Homology is -complete
Ryu Hayakawa
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…
quant-ph2026
Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
Dominic Lowe, M. S. Kim, Roberto Bondesan +1
Topological data analysis (TDA) is a machine learning technique that uses topology to extract patterns from data and has shown the potential to exhibit quantum advantage. A key con…
quant-ph2025
Computational complexity of the homology problem with orientable filtration: MA-completeness
Ryu Hayakawa, Casper Gyurik, Mahtab Yaghubi Rad +1
We show the existence of an MA-complete homology problem for a certain subclass of simplicial complexes. The problem is defined through a new concept of orientability of simplicial…