Alexander Schmidhuber, Seth Lloyd, Michele Reilly, Paolo Zanardi, Aaron Lauda (Jan 23 2025).
Abstract: Khovanov homology is a topological knot invariant that categorifies the Jones polynomial, recognizes the unknot, and is conjectured to appear as an observable in
4D supersymmetric Yang--Mills theory. Despite its rich mathematical and physical significance, the computational complexity of Khovanov homology remains largely unknown. To address this challenge, this work initiates the study of efficient quantum algorithms for Khovanov homology. We provide simple proofs that increasingly accurate additive approximations to the ranks of Khovanov homology are DQC1-hard, BQP-hard, and #P-hard, respectively. For the first two approximation regimes, we propose a novel quantum algorithm. Our algorithm is efficient provided the corresponding Hodge Laplacian thermalizes in polynomial time and has a sufficiently large spectral gap, for which we give numerical and analytical evidence. Our approach introduces a pre-thermalization procedure that allows our quantum algorithm to succeed even if the Betti numbers of Khovanov homology are much smaller than the dimensions of the corresponding chain spaces, overcoming a limitation of prior quantum homology algorithms. We introduce novel connections between Khovanov homology and graph theory to derive analytic lower bounds on the spectral gap.
