論文の概要: A quantum algorithm for Khovanov homology

• arxiv url: http://arxiv.org/abs/2501.12378v1
• Date: Tue, 21 Jan 2025 18:54:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-22 14:20:28.030740
• Title: A quantum algorithm for Khovanov homology
• Title（参考訳）: ホバノフホモロジーのための量子アルゴリズム
• Authors: Alexander Schmidhuber, Seth Lloyd, Michele Reilly, Paolo Zanardi, Aaron Lauda,
• Abstract要約: ホバノフホモロジー(Khovanov homology)は、ジョーンズ位相不変量を分類し、カンノットを認識する結び目であり、4D$超対称ヤン・ミルズ理論において観測可能であると推測されている。 リッチな数学的および物理的重要性にもかかわらず、ホバノフホモロジーの計算複雑性はほとんど不明である。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: ホバノフホモロジー(Khovanov homology)は、ジョーンズ多項式を分類し、カンノットを認識する位相的結び目不変量であり、4D$超対称ヤングル-ミルズ理論において観測可能であると推測される。 リッチな数学的および物理的重要性にもかかわらず、ホバノフホモロジーの計算複雑性はほとんど不明である。 この課題に対処するため、この研究はホバノフホモロジーのための効率的な量子アルゴリズムの研究を開始する。 ホバノフホモロジーの階数に対するより正確な加法近似は、それぞれ DQC1-hard と BQP-hard と #P-hard である、という単純な証明を提供する。 最初の2つの近似規則について,新しい量子アルゴリズムを提案する。 我々のアルゴリズムは多項式時間で対応するホッジ・ラプラシアン熱化を仮定し,十分に大きなスペクトルギャップを持ち,数値的および解析的証拠を与える。 提案手法では, ホバノフホモロジーのベッチ数が対応する鎖空間の次元よりもはるかに小さい場合でも, 従来の量子ホモロジーアルゴリズムの制限を克服して, 量子アルゴリズムを成功させることができる。 我々は、スペクトルギャップに関する解析的下界を導出するために、ホバノフホモロジーとグラフ理論の間の新しい接続を導入する。

関連論文リスト

• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Quantum Bayesian Optimization [64.58749619145908]
  本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。 O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。 線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
  論文  参考訳（メタデータ） (2023-10-09T03:10:42Z)
• Elementary Proof of QAOA Convergence [0.0]
  量子交互作用素 Ansatz (QAOA) に対する厳密な収束の証明を提供する。 この証明は量子断熱アルゴリズムとQAOAの接続を追従することを含み、自然に位相分離器とミキサーのキーワードの洗練された定義を示唆している。
  論文  参考訳（メタデータ） (2023-02-09T22:57:59Z)
• Optimal lower bounds for Quantum Learning via Information Theory [3.093890460224435]
  我々は、PACとモデルの両方において、情報理論的アプローチにより、量子サンプルの複雑さに対して最適な下界を導出する。 次に、確率論から古典的な問題であるクーポンコレクタ問題(英語版)の量子アナログに目を向ける。 量子クーポンコレクター問題のすべての側面は、関連するグラム行列のスペクトルの性質について研究する。
  論文  参考訳（メタデータ） (2023-01-05T18:55:04Z)
• Adapting the HHL algorithm to quantum many-body theory [0.0]
  我々は,光分子系における相関エネルギーの正確な予測を行うために,Harrow-Hassidim-Lloydアルゴリズムを実装した。 量子コンピューティングのさまざまな時代におけるHHLの変種について紹介する。 我々は、相関エネルギーを正確に捉えるために、NISQ型AdaptHHLiteの能力を実証する。
  論文  参考訳（メタデータ） (2022-12-30T15:38:59Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions [4.2698418800007865]
  古典ハミルトニアンの分配関数を所定の温度で近似するための古典的および量子的アルゴリズムを提案する。 我々は,vStefankovivc,Vempala,Vigodaの古典的アルゴリズムを改良し,サンプルの複雑さを改善する。 我々はこの新しいアルゴリズムを量子化し、HarrowとWeiにより、この問題に対してこれまで最速の量子アルゴリズムを改善した。
  論文  参考訳（メタデータ） (2020-09-23T17:27:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。