論文の概要: A Complete Proof of $\mathsf{QMA}_1$-Hardness for Weighted Gapped Clique Homology
- arxiv url: http://arxiv.org/abs/2610.03584v1
- Date: Fri, 02 Oct 2026 16:55:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-06 00:14:30.494406
- Title: A Complete Proof of $\mathsf{QMA}_1$-Hardness for Weighted Gapped Clique Homology
- Title（参考訳）: 重み付きGapped Clique Homologyに対する$\mathsf{QMA}_1$-Hardnessの完全証明
- Abstract要約: 我々は、cliqueホモロジーのハード方向の完全な証明を与える。
固定効率計算可能な$k(n)$と逆多項式$(n)$の場合、重み付きギャップ付きクリッドホモロジーは$mathsfQMA_1(mathcal G)$-hardである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The computational complexity of simplicial homology has been studied since the question was raised by Kaibel and Pfetsch, and clique homology was later shown to be $\mathsf{QMA}_1$-hard by Crichigno and Kohler. King and Kohler subsequently introduced the weighted, spectrally gapped version considered here and developed a reduction intended to establish the same hardness result in this setting. We give a complete proof of the hard direction. The earlier King-Kohler argument contains a gap in the analysis of the nontrivially folded local gadgets, so the required topological and spectral properties have to be re-established on the clique complexes actually produced by the reduction. This is not a local repair of the published proof: the argument requires a new analysis of the local topology, the filtered cochain complexes, and the interaction of many overlapping gadgets. Our proof uses exact finite certificates for the local combinatorial data and relative homology to determine the effect of each gadget on the encoded qubit space. We then prove the finite-dimensional filtered-Hodge statement needed to recover the corresponding rank-one low-energy penalty and derive a quantitative global estimate that transfers the source-Hamiltonian promise gap to the final weighted Hodge Laplacian. Consequently, for fixed efficiently computable $k(n)$ and inverse-polynomial $γ(n)$, weighted gapped clique homology is $\mathsf{QMA}_1(\mathcal G)$-hard. The previously known $\mathsf{QMA}$-containment argument is logically independent of the gap and remains unaffected.
- Abstract（参考訳）: 単純ホモロジーの計算複雑性は、カイベルとプフェッチュが疑問を提起してから研究され、後にクリニニョとコーラーによって、clique homology は $\mathsf{QMA}_1$-hard であることが示されている。
キングとコーラーはその後、ここで検討された重み付けされたスペクトルギャップのあるバージョンを導入し、この設定で同じ硬さを確立することを目的とした縮小を開発した。
我々はその厳しい方向の完全な証明を与える。
初期のKing-Kohlerの議論は、非自明に折り畳まれた局所ガジェットの分析におけるギャップを含んでいるため、要求される位相的およびスペクトル的性質は、実際に還元によって生成されるクリッド錯体上で再確立する必要がある。
これは公表された証明の局所的な修復ではなく、この議論は局所的なトポロジー、フィルターされたコチェーン錯体、および多くの重なり合うガジェットの相互作用の新しい分析を必要とする。
我々の証明では、局所組合せデータと相対ホモロジーの正確な有限証明を用いて、各ガジェットが符号化された量子ビット空間に与える影響を決定する。
次に、対応するランク1の低エネルギーペナルティを回復するために必要な有限次元フィルタ・ホッジステートメントを証明し、ソース・ハミルトン約束ギャップを最終重み付きホッジ・ラプラシアンに転送する定量的な大域的推定を導出する。
したがって、固定された計算可能$k(n)$と逆多項式$γ(n)$の場合、重み付きギャップ付きクリッドホモロジーは$\mathsf{QMA}_1(\mathcal G)$-hardである。
前述した$\mathsf{QMA}$-containmentの引数は、ギャップから論理的に独立であり、影響を受けない。
関連論文リスト
- On the SoS Certifiability of Log-Concave Distributions [51.56484100374058]
圏 $(Cm)m|v|m - mathbbE_Xsim Plangle X,vranglem$ は、すべての偶数 mge2$ に対する平方の和であり、$C>0$ は普遍定数である。
これにより、コタリとシュタインハルト(arXiv:1711.07465)の定理におけるポアンカレ定数への依存を排除し、対数凹面分布の最適モーメント境界を回復する。
論文 参考訳（メタデータ） (2026-09-24T16:48:02Z) - Torsion detection in clique complexes is conditionally $QMA_1$-hard [0.0]
傾斜錯体におけるねじれ検出は, 一定のギャップ約束の下でも, NP$ハードであることを示す。
積分ホモロジーはラプラススペクトルに到達できない情報を含んでいる。
傾斜錯体におけるねじれの検出は、一定のギャップの約束の下でも、NP$ハードである。
論文 参考訳（メタデータ） (2026-09-12T19:14:49Z) - 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) - Theory of the Matchgate Commutant [0.0]
異なるシステムコピーを結合する作用素がリー代数 $mathfrakso(k)$ を生成し、リッチでトラクタブルな構造を持つ不変量の空間を与えることを示す。
また、Clifford-matchgate 部分群の可換性を特徴付け、マヨラナモードの符号付き置換に制限を加えることで、$k geq 4$ レプリカに対してマッチゲートの場合から定性的に発散する可換性が得られることを示す。
論文 参考訳（メタデータ） (2026-03-12T19:12:19Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities [51.320599504997745]
統計物理学からの予測では、ブロックモデル(SBM)におけるコミュニティの回復は、上述の時間で可能であり、上述のケステンスティグム(KS)しきい値のみである。
Chinら(2025)は、最近、スパース体制では、非バックトラック経路を数えることにより、KS閾値以下でコミュニティの回復が可能であることを証明した。
論文 参考訳（メタデータ） (2025-09-19T09:53:56Z) - Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文 参考訳（メタデータ） (2023-11-28T21:15:30Z) - Annihilating Entanglement Between Cones [77.34726150561087]
ローレンツ錐体は、ある種の強いレジリエンス特性を満たす対称基底を持つ唯一の円錐体であることを示す。
我々の証明はローレンツ・コーンの対称性を利用しており、エンタングルメント蒸留のプロトコルに類似した2つの構造を適用している。
論文 参考訳（メタデータ） (2021-10-22T15:02:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。