Fugu-MT 論文翻訳(概要): Unweighted Gapped Clique Homology is $\mathsf{QMA}

論文の概要: Unweighted Gapped Clique Homology is $\mathsf{QMA}_1$-complete

arxiv url: http://arxiv.org/abs/2608.02726v1
Date: Mon, 03 Aug 2026 18:00:02 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-05 15:30:22.908305
Title: Unweighted Gapped Clique Homology is $\mathsf{QMA}_1$-complete
Title（参考訳）: 非重み付きGapped Clique Homology is $\mathsf{QMA}_1$-complete
Abstract要約: 私たちは、$mathsfQMA$1g$が$mathsfQMA$1g$であり、ユニバーサルゲートセット$g=mathsfX,mathsfCX,mathsfCCX,Hotimes H$であることを示す。ブロックサイズは、対称平均が重み付きホッジ計量を再現するように選択される。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Deciding whether the clique complex of a given graph has nontrivial homology in a given dimension, under vertex-product weighting and an inverse-polynomial spectral gap promise on the combinatorial Hodge Laplacian, is known to be $\mathsf{QMA}_1$-hard and contained in $\mathsf{QMA}$ by King and Kohler (FOCS 2024). The vertex weights are essential in the known proof, where they provide the scale separation needed for the spectral gap analysis. We prove that, when every vertex has weight one, the problem remains $\mathsf{QMA}_1^{g_2}$-hard and is contained in $\mathsf{QMA}_1^{g_2}$, where $\mathsf{QMA}_1^{g_2}$ is $\mathsf{QMA}_1$ with the universal gate set $g_2=\{\mathsf{X},\mathsf{CX},\mathsf{CCX},H\otimes H\}$. The construction replaces weight by expansion: each vertex of the weighted complex is blown up into a clique whose size encodes its weight. The block sizes are chosen so that symmetric averages reproduce the weighted Hodge metric. The symmetric sector therefore carries the weighted Laplacian up to a common scalar factor, while a local averaging argument gives a uniform lower bound on the orthogonal complement to the symmetric sector. Hence the weighted gap analysis transfers to an unweighted clique complex without introducing either additional low-energy states or spurious homology. Containment in $\mathsf{QMA}_1^{g_2}$ follows from Rudolph's exact linear combination of unitaries simulation of sparse integer clique Laplacians. The result shows that the gap promise, rather than vertex weighting, is the source of the complexity of gapped clique homology.
Abstract（参考訳）: 与えられたグラフのクリッド複体が与えられた次元において非自明なホモロジーを持つかどうかを決定づけると、頂点積重み付けと合成ホッジ・ラプラシアンの逆多項式スペクトルギャップの公約は$\mathsf{QMA}_1$-hardであり、King and Kohler (FOCS 2024) の$\mathsf{QMA}$に含まれる。頂点重みは既知の証明において必須であり、スペクトルギャップ解析に必要なスケール分離を提供する。すべての頂点がウェイト 1 を持つとき、問題は $\mathsf{QMA}_1^{g_2}$-hard であり、$\mathsf{QMA}_1^{g_2}$, $\mathsf{QMA}_1^{g_2}$, $\mathsf{QMA}_1$,\mathsf{X},\mathsf{CX},\mathsf{CCX},H\otimes H\}$ に含まれる。重み付けされた複合体の各頂点は、その大きさが重みをエンコードする斜めに吹き飛ばされる。ブロックサイズは、対称平均が重み付きホッジ計量を再現するように選択される。したがって、対称セクターは重み付きラプラシアンを共通のスカラー因子まで持ち込み、一方局所平均論法は対称セクターの直交補集合上の一様下界を与える。したがって、重み付きギャップ解析は、追加の低エネルギー状態や急激なホモロジーを導入することなく、非重み付きクリプト錯体に転移する。 $\mathsf{QMA}_1^{g_2}$ の包含は、スパース整数clique Laplacian のユニタリシミュレーションの正確な線形結合から従う。この結果は、頂点重み付けよりもギャップ公約が、ギャップ付き斜めホモロジーの複雑さの源であることを示している。

関連論文リスト

Torsion detection in clique complexes is conditionally $QMA_1$-hard [0.0]
傾斜錯体におけるねじれ検出は, 一定のギャップ約束の下でも, NP$ハードであることを示す。積分ホモロジーはラプラススペクトルに到達できない情報を含んでいる。傾斜錯体におけるねじれの検出は、一定のギャップの約束の下でも、NP$ハードである。
論文参考訳（メタデータ） (2026-09-12T19:14:49Z)
A quantum oracle separation between QMA(2) and QMA [0.9068953081227296]
量子相対は、$mathsfQMA neq mathsfQMA(2)$である。すべての$+1$に対して、任意の$(, symmetric)$-disentanglerは出力キュービット数で指数関数的な入力サイズを必要とする。
論文参考訳（メタデータ） (2026-09-02T17:50:05Z)
Topology of the Set of Entangled State [0.0]
ここでは、$mathsf E$ はパス接続であり、2ビットの場合を除いて単に接続されていることを示す。この例外的な場合、$mathsf E$ は極大交絡状態の集合とホモトピー同値であることが判明した。
論文参考訳（メタデータ） (2026-07-20T16:04:26Z)
Non-Perturbative Closed Form for the Typical Bipartite Mutual Information of Haar-Random States [7.7281318046635015]
この量には1つの非摂動閉形式がある。 $langle I(A:B)rangle = (d_A2-1)(d_B2-1),mathcalG(d_A,d_B,d_E)$, ここで$mathcalG$はボース-アインシュタイン核上の明示収束積分によって与えられる。
論文参考訳（メタデータ） (2026-05-28T10:19:40Z)
Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。本研究の主な成果は,PAC学習の基本定理のスケール敏感な一般化である。また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。
論文参考訳（メタデータ） (2026-05-13T15:41:30Z)
Spectral statistics and energy-gap scaling in $k-$local spin Hamiltonians [0.0]
正確な$k$スピンに作用する全ての相互作用するスピンハミルトニアンのスペクトル特性について検討する。 $mu = 0$ の場合、ランダム行列のアンサンブルはシステムサイズ $L$ と局所性 $k$ のパリティによって決定されることを示す。本研究では,確率行列統計学の普遍的特徴とスペクトルギャップ形成を捉える半可解モデルを提案する。
論文参考訳（メタデータ） (2025-10-17T17:11:38Z)
Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。複雑性は量子複雑性クラスによって特徴づけられる。我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文参考訳（メタデータ） (2023-11-28T21:15:30Z)
A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文参考訳（メタデータ） (2023-09-25T17:54:19Z)
Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文参考訳（メタデータ） (2022-08-19T18:00:34Z)
Monogamy of entanglement between cones [43.57338639836868]
モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
論文参考訳（メタデータ） (2022-06-23T16:23:59Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文参考訳（メタデータ） (2021-06-27T17:25:24Z)
Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文参考訳（メタデータ） (2021-06-25T17:03:38Z)
Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
論文参考訳（メタデータ） (2021-04-26T15:03:08Z)

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

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