論文の概要: Torsion detection in clique complexes is conditionally $QMA_1$-hard

• arxiv url: http://arxiv.org/abs/2609.14110v1
• Date: Sat, 12 Sep 2026 19:14:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.687917
• Title: Torsion detection in clique complexes is conditionally $QMA_1$-hard
• Title（参考訳）: 条件付き$QMA_1$-hardの斜方体におけるねじり検出
• Abstract要約: 傾斜錯体におけるねじれ検出は, 一定のギャップ約束の下でも, NP$ハードであることを示す。 積分ホモロジーはラプラススペクトルに到達できない情報を含んでいる。 傾斜錯体におけるねじれの検出は、一定のギャップの約束の下でも、NP$ハードである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combinatorial Laplacian. Deciding whether a Betti number of a clique complex is nonzero is $QMA_1$-hard, and remains so under a spectral gap promise on vertex-weighted graphs. Integral homology, however, contains information inaccessible to the Laplacian spectrum. A new part that appears in integral homology is torsion: cycles that become boundaries only after being traversed several times, as in a projective plane or a Klein bottle. We ask how hard it is to detect torsion, and we answer with a simple reduction. We attach to an arbitrary clique complex a fixed $31$-vertex triangulation of the projective plane. The $k$th mod-$2$ Betti number of the input then reappears as $2$-torsion two degrees up, while all rational homology disappears and every combinatorial Laplacian acquires a constant spectral gap. We conclude that detecting torsion in clique complexes of unweighted graphs is $NP$-hard, even under a constant gap promise, and that it is $QMA_1$-hard if mod-$2$ clique homology is.
• Abstract（参考訳）: トポロジカルデータ解析のための量子アルゴリズムは、単純複体のホモロジー群のランクであるベッチ数を計算する。 クリッド複体のベッチ数が 0 でないかどうかを決めることは、QMA_1$-hard であり、頂点重み付きグラフのスペクトルギャップ公約の下にある。 しかし、積分ホモロジーはラプラススペクトルに到達できない情報を含んでいる。 積分ホモロジーに現れる新しい部分はねじれであり、射影平面やクラインのボトルのように、数回渡った後に境界となるサイクルである。 トーションを検出するのがどれほど難しいのかを尋ね、簡単な還元で答える。 任意の斜め複体に固定された311ドル頂点三角形の射影平面を取り付ける。 入力の$k$th mod-$2$ Betti 番号は、2$-torsion 2 degrees として再現れるが、すべての有理ホモロジーは消え、すべての組合せラプラシアンは一定のスペクトルギャップを得る。 我々は、非重み付きグラフのクリッド複体におけるトーションの検出は、一定のギャップ約束の下でも、$NP$-hardであり、 mod-$2$-hard であれば$QMA_1$-hard である、と結論付けた。

関連論文リスト

• Unweighted Gapped Clique Homology is $\mathsf{QMA}_1$-complete [0.0]
  私たちは、$mathsfQMA$1g$が$mathsfQMA$1g$であり、ユニバーサルゲートセット$g=mathsfX,mathsfCX,mathsfCCX,Hotimes H$であることを示す。 ブロックサイズは、対称平均が重み付きホッジ計量を再現するように選択される。
  論文  参考訳（メタデータ） (2026-08-03T18:00:02Z)
• A Spectral Proof of the Hypergraph Moore Bound [46.26532142699448]
  ハイパーグラフムーア境界に関するファイゲの2008年の予想を証明する。 すべての$kge3$と$1leellle n$に対して、$n$ vertices 上の任意の $k$-uniform hypergraph は、$C,nk/2/ellk/2-1$ hyperedges は、最大$A,elllog(en/ell)$で偶数被覆を含む。
  論文  参考訳（メタデータ） (2026-07-28T17:38:31Z)
• Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence [0.0]
  隠れた$d$正規基底グラフを識別するための量子アルゴリズムを、その難解バージョンへのアクセスから$n$頂点に$G$を与える。 我々のアルゴリズムは概念的には単純で、$G_rm spire$ 上で連続時間ウォークし、古典的には pret*$ で 1 つのアダマールテストを行う。
  論文  参考訳（メタデータ） (2026-05-11T20:44:32Z)
• Universal Complex Quantum-Like Bits from Hermitian Weighted Graphs [0.0]
  ブロック結合正則グラフは、所定の複素量子様ビット状態を正確な同期固有状態として実現できる。 完全に離散なエルミート実現はシンクロナイズドされた純粋状態空間において密であることを示す。
  論文  参考訳（メタデータ） (2026-04-27T03:09:53Z)
• Mesoscopic Fluctuations and Multifractality at and across Measurement-Induced Phase Transition [46.176861415532095]
  二次元自由フェルミオンモデルにおける量子軌道のアンサンブルに関する統計的揺らぎについて検討する。 この結果はアンダーソンの局所化に顕著な類似性を示し、G_AB$は2末端の導電率に対応する。 監視システムのメソスコピック理論の基礎を築き,様々な拡張への道を開いた。
  論文  参考訳（メタデータ） (2025-07-15T13:44:14Z)
• Geometric bound on structure factor [44.99833362998488]
  我々は、$k$-空間の量子幾何テンソルの二次形式が、静的構造係数$S(q)$の$q4$項上の有界を小さく$vecq$とすることを示した。 この境界を飽和するバンドは、ラプラス方程式に類似した条件を満たすため、これらを $textitharmonic bands$ と呼ぶ。
  論文  参考訳（メタデータ） (2024-12-03T18:30:36Z)
• Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
  計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。 複雑性は量子複雑性クラスによって特徴づけられる。 我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
  論文  参考訳（メタデータ） (2023-11-28T21:15:30Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Complete crystalline topological invariants from partial rotations in (2+1)D invertible fermionic states and Hofstadter's butterfly [6.846670002217106]
  多体不変量 $Theta_textopm$, where $texto$ is a high symmetric point, from partial rotations in (2+1)D invertible fermionic states。 この結果は,従来の研究とは対照的に,磁場とチャーン数$C neq 0$の存在に適用できる。
  論文  参考訳（メタデータ） (2023-03-29T18:00:00Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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