A quantum algorithm for Khovanov homology

• URL: http://arxiv.org/abs/2501.12378v2
• Date: Thu, 23 Jan 2025 20:54:24 GMT
• Title: A quantum algorithm for Khovanov homology
• Authors: Alexander Schmidhuber, Michele Reilly, Paolo Zanardi, Seth Lloyd, Aaron Lauda,
• Abstract summary: Khovanov homology is a knot that categorifies the Jones topological invariant, 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.
• Score: 42.6618666851542
• License:
• 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.

Related papers

• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
  arXiv  Detail & Related papers  (2024-03-22T18:00:03Z)
• Quantum Bayesian Optimization [64.58749619145908]
  We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
  arXiv  Detail & Related papers  (2023-10-09T03:10:42Z)
• Elementary Proof of QAOA Convergence [0.0]
  We provide a rigorous proof of convergence for the Quantum Alternating Operator Ansatz (QAOA) The proof involves retracing the connection between the Quantum Adiabatic Algorithm and the QAOA, and naturally suggests a refined definition of the phase separator' and mixer' keywords.
  arXiv  Detail & Related papers  (2023-02-09T22:57:59Z)
• Optimal lower bounds for Quantum Learning via Information Theory [3.093890460224435]
  We derive optimal lower bounds for quantum sample complexity in both the PAC and models via an information-theoretic approach. We then turn to a quantum analogue of the Coupon Collector problem, a classic problem from probability theory. All the aspects of the Quantum Coupon Collector problem we study rest on properties of the spectrum of the associated Gram matrix.
  arXiv  Detail & Related papers  (2023-01-05T18:55:04Z)
• Adapting the HHL algorithm to quantum many-body theory [0.0]
  We implement the Harrow-Hassidim-Lloyd (HHL) algorithm to make precise predictions of correlation energies for light molecular systems. We introduce the following variants of HHL for different eras of quantum computing. We demonstrate the ability of the NISQ variant of AdaptHHLite to capture correlation energy precisely.
  arXiv  Detail & Related papers  (2022-12-30T15:38:59Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions [4.2698418800007865]
  We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. We modify the classical algorithm of vStefankovivc, Vempala and Vigoda to improve its sample complexity. We quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei.
  arXiv  Detail & Related papers  (2020-09-23T17:27:28Z)

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.