論文の概要: Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$

• arxiv url: http://arxiv.org/abs/2311.17234v2
• Date: Sun, 06 Oct 2024 23:00:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-08 13:12:03.711459
• Title: Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$
• Title（参考訳）: Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$
• Authors: Robbie King, Tamara Kohler,
• Abstract要約: 計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。 複雑性は量子複雑性クラスによって特徴づけられる。 我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space $X$ and an integer $k$, decide if $X$ contains a $k$-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics. We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every $k+1$-clique in the graph to be a $k$-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is $\text{QMA}_1$-hard and contained in $\text{QMA}$. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as \emph{spectral sequences}. In particular, we exploit a connection between spectral sequences and Hodge theory. Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work. Our result provides some suggestion that the quantum TDA algorithm \emph{cannot} be dequantized. More broadly, we hope that our results will open up new possibilities for quantum advantage in topological data analysis.
• Abstract（参考訳）: 計算トポロジーにおける古典問題、ホモロジー問題:ある空間$X$と整数$k$の説明が与えられたとき、$X$が$k$次元の穴を持つかどうかを決定する。 ホモロジー問題の設定とステートメントは完全に古典的であるが、複雑性は量子複雑性クラスによって特徴づけられる。 この結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。 我々は、トポロジカルデータ解析(TDA)の実践的応用に動機づけられた斜方体を考察する。 グラフのclique complex(英語版)は、グラフのすべての$k+1$-cliqueを$k$-simplex(英語版)と宣言することによって形成される単純複素体である。 我々の主な結果は、重み付きグラフのclique complexが穴を持つかどうかを判断し、そのギャップに適切な約束が与えられると、$\text{QMA}_1$-hard となり、$\text{QMA}$ に含まれる。 我々の主な革新は、組合せラプラシア作用素の固有値を下げる手法である。 このため、代数的トポロジーからツールを「emph{spectral sequences}」と呼ぶ。 特に、スペクトル列とホッジ理論の接続を利用する。 スペクトル列は、組合せラプラシアンに対する摂動理論に類似した役割を果たす。 また,本研究は,従来の作業で用いられる外科手術技術を開発した。 この結果は、量子TDAアルゴリズム \emph{cannot} が不等化されることを示唆している。 より広範に、我々の結果は、トポロジカルデータ分析における量子優位性の新しい可能性を開くことを願っている。

関連論文リスト

• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。 次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• New Approaches to Complexity via Quantum Graphs [0.0]
  量子グラフに対するclique問題を紹介し,研究する。 我々の問題に対する入力は、回路によって誘導される量子チャネルとして表現される。 言語内のチャネルのコレクションを変更することで、これらがクラス$textsfNP$, $textsfMA$, $textsfQMA$, $textsfQMA(2)$の完全な問題を引き起こします。
  論文  参考訳（メタデータ） (2023-09-22T14:20:14Z)
• Quantum Algorithm for Estimating Betti Numbers Using a Cohomology Approach [2.2000560351723504]
  ベティの数値を古典的に計算することは膨大な量のデータのために大変な作業である。 ホッジ理論とド・ラムコホモロジーにインスパイアされた「双対」アプローチを考える。 我々のアルゴリズムは、その$r$-th Betti number $beta_r$を乗算誤差まで計算できる。
  論文  参考訳（メタデータ） (2023-09-19T17:44:53Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Clique Homology is QMA1-hard [0.0]
  simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。 これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。 本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
  論文  参考訳（メタデータ） (2022-09-23T18:14:16Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。 単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:59:41Z)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  我々は,不一致の最小化と(量子)通信複雑性の新たな関連性を開発する。 対称$n times n$$A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ に対し、pm 1n において $sum_i leq n x_i A_i$ の最大固有値が最大となる符号 $x が存在することを示す。
  論文  参考訳（メタデータ） (2021-10-19T16:51:11Z)
• Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
  我々は、$mathcal N=2 $ 超対称性を持つフェルミオンハミルトニアンの文脈における局所ハミルトニアン問題の複雑さを考える。 これを研究する主な動機は、超対称系の基底状態エネルギーがちょうどゼロであることと、あるコホモロジー群が非自明であることである。
  論文  参考訳（メタデータ） (2021-06-30T18:00:01Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)

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

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