There is a neat correspondence between the question of whether a simplicial complex has a k-dimensional hole and whether the ground state of a related supersymmetric (SUSY) quantum many-body Hamiltonian is at zero energy:
Complexity of Supersymmetric Systems and the Cohomology Problem
Clique Homology is QMA1-hard
A less technical presentation of the latter paper at QIP2023 and can be viewed here.
Both problems are QMA1-hard, meaning that the correctness of a trial solution can be efficiently checked by a quantum computer (but finding the correct solution remains hard even for the quantum computer). In contrast, recently-proposed quantum algorithms for TDA consider relaxations of the homology problem that can be solved efficiently using quantum algorithms, such as estimating the normalized number of k-cycles to some finite precision.
What other seemingly classical or purely mathematical problems can be naturally framed in the language of supersymmetric quantum mechanics? This promises to be fertile ground for exponential quantum speedups, and you don't need to be an expert in quantum algorithms to join the hunt!
No comments:
Post a Comment