論文の概要: Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness $\&$ An Algorithm for Torsion Witness

• arxiv url: http://arxiv.org/abs/2609.28112v1
• Date: Wed, 23 Sep 2026 13:44:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 00:05:18.048507
• Title: Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness $\&$ An Algorithm for Torsion Witness
• Title（参考訳）: ベティ数を超えた量子トポロジカルデータ分析:複雑度ハードネス$$&$のトーション幅アルゴリズム
• Abstract要約: ホモロジーはトーションの形で追加の情報を含んでいる。 我々は古典的視点と量子的視点の両方からトーションを研究する。 我々は一方のトーション証人として機能する量子アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent advances have revealed an interplay between quantum computing and topological data analysis (TDA). Most quantum TDA has focused on Betti numbers, which characterize the connectivity and ``holes'' of a dataset. Homology, however, contains additional information in the form of torsion: a nontrivial cycle can become trivial after being repeated finitely, revealing global constraints on how cycles combine and wrap around one another. Beyond applications in biomolecular studies, torsion appears in physical settings including homological quantum rotor codes, discrete charges, and gauge sectors. We study torsion from both classical and quantum perspectives. Given a graph $G$ and its clique complex $K = \mathrm{Cl}(G)$, we first prove that, for fixed $r$ and prime $p$, deciding whether $H_r(K,\mathbb{Z})$ contains $p$-torsion is NP-hard. As a corollary, when a homological rotor code is specified by $G$, deciding whether the code has a finite-dimensional logical sector of a given order is NP-hard. We discuss related problems, including the Bockstein homomorphism, Smith normal form, lattice saturation, and cohomology. Second, for a finite set of primes $P$, we develop a quantum algorithm that serves as a one-sided torsion witness. For fixed $r$, it outputs WITNESS or INCONCLUSIVE, i.e. WITNESS certifies that either $H_r(K,\mathbb{Z})$ or $H_{r-1}(K,\mathbb{Z})$ contains $p$-torsion for some $p\in P$ while INCONCLUSIVE makes no claim about its presence or absence. We identify a regime in which the algorithm achieves a near-quadratic quantum speedup over the corresponding classical algorithm under the same input model. Our NP-hardness result complements recent hardness results for estimating Betti numbers, adding a complexity-theoretic perspective to quantum TDA. Together, these results demonstrate that integral homology, beyond its Betti numbers, can be computationally challenging.
• Abstract（参考訳）: 最近の進歩は、量子コンピューティングとトポロジカルデータ分析(TDA)の相互作用を明らかにしている。 ほとんどの量子TDAは、データセットの接続性と‘holes’を特徴付けるベッチ数に重点を置いている。 しかし、ホモロジーはトーションの形で追加の情報を含む:非自明なサイクルは有限に繰り返すと自明になり、サイクルが互いに結合し包む方法に関する大域的な制約が明らかになる。 生体分子研究の応用以外にも、トーションはホモロジー量子ローター符号、離散電荷、ゲージセクターなどの物理的設定に現れる。 我々は古典的視点と量子的視点の両方からトーションを研究する。 グラフ $G$ とそのclique complex $K = \mathrm{Cl}(G)$ が与えられたとき、まず、固定 $r$ と素 $p$ に対して、$H_r(K,\mathbb{Z})$ が NP-ハードであるかどうかを決定する。 結果として、ホモロジカルローターコードが$G$で指定されると、与えられた順序の有限次元論理セクターがNPハードであるかどうかが決定される。 ボクシュタイン準同型、スミス正規形式、格子飽和、コホモロジーなどの関連する問題について議論する。 第二に、有限個の素数の集合 P$ に対して、一方のトーションの証人として機能する量子アルゴリズムを開発する。 固定$r$の場合、WITNESSまたはINCONCLUSIVEを出力する。すなわち、WITNESSは$H_r(K,\mathbb{Z})$または$H_{r-1}(K,\mathbb{Z})$のいずれかが、ある$p\in P$に対して$p$-torsionを含むことを証明している。 同じ入力モデルの下で、対応する古典的アルゴリズムに対して、アルゴリズムが準四進法に近い量子スピードアップを達成する仕組みを同定する。 我々のNP硬度結果はベッチ数の推定に最近の硬度結果を補完し、量子TDAに複雑性理論的な視点を加える。 これらの結果は、ベッチ数以外の積分ホモロジーが計算的に困難であることを証明している。

関連論文リスト

• Torsion detection in clique complexes is conditionally $QMA_1$-hard [0.0]
  傾斜錯体におけるねじれ検出は, 一定のギャップ約束の下でも, NP$ハードであることを示す。 積分ホモロジーはラプラススペクトルに到達できない情報を含んでいる。 傾斜錯体におけるねじれの検出は、一定のギャップの約束の下でも、NP$ハードである。
  論文  参考訳（メタデータ） (2026-09-12T19:14:49Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。 任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
  論文  参考訳（メタデータ） (2026-07-22T07:41:32Z)
• Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning [0.3277163122167433]
  有限サイズの量子回路によって生成される量子データに対する情報理論オッカム理論を開発した。 M$コピーで、G$-gate近似エラーと統計的ペナルティを学習できる。 我々のフレームワークは、有界回路の複雑さを量子機械学習のモデル選択原理に変える。
  論文  参考訳（メタデータ） (2026-06-10T15:28:36Z)
• Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors [40.72140849821964]
  我々は、任意の数のフェルミオンフレーバーを持つ巨大なThiringとGross-Neveuモデルを、大きさ$L$の空間1次元格子上で離散化した$N_f$と考えている。 我々は、N_f = 1,2,3,4$の20キュービットまでのシステムサイズに優れた忠実度を持つ両モデルの基底状態を作成する。 我々の研究は、大規模なN_f$フェルミオン量子場理論モデルのリアルタイムダイナミクスの量子シミュレーションに向けた具体的なステップである。
  論文  参考訳（メタデータ） (2026-02-25T19:00:01Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。 レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
  論文  参考訳（メタデータ） (2025-10-09T17:37:33Z)
• A Quantum Algorithm For Computing Contextuality Bounds [0.0]
  我々はGroverの探索アルゴリズムに基づく量子アルゴリズムを提供し、古典的なブルート力法よりも高速な$O(sqrtn loglogn)$$$$O(sqrtn loglogn)$O(sqrtn loglogn)$O(n$)$O(sqrtn loglogn)$の文脈性を計算する。 また,基本状態の位相に関連情報をエンコードし,回路幅と深度要件を低減させるGroverのバリエーションについても検討した。
  論文  参考訳（メタデータ） (2025-09-24T15:36:02Z)
• Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
  計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。 複雑性は量子複雑性クラスによって特徴づけられる。 我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
  論文  参考訳（メタデータ） (2023-11-28T21:15:30Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)

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

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