論文の概要: Promise Clique Homology on weighted graphs is $\text{QMA}_1$-hard and
contained in $\text{QMA}$
- arxiv url: http://arxiv.org/abs/2311.17234v1
- Date: Tue, 28 Nov 2023 21:15:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-30 23:14:39.528587
- Title: Promise Clique Homology on weighted graphs is $\text{QMA}_1$-hard and
contained in $\text{QMA}$
- Title（参考訳）: 重み付きグラフ上のPromise Clique Homologyは$\text{QMA}_1$-hardであり、$\text{QMA}$に含まれる
- Authors: Robbie King, Tamara Kohler
- Abstract要約: 計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
この結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- 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
[Wit82].
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, 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 spectral sequences. In particular, we exploit a connection
between spectral sequences and Hodge theory [For94]. 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
[CK22].
Our result provides some suggestion that the quantum TDA algorithm [LGZ16]
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$次元の穴を持つかどうかを決定する。
ホモロジー問題の設定とステートメントは完全に古典的であるが、複雑性は量子複雑性クラスによって特徴づけられる。
我々の結果はホモロジーと超対称量子力学 [Wit82] の接続の側面と見なすことができる。
我々は、トポロジカルデータ解析(TDA)の実践的応用を動機とする斜方体を考察する。
グラフのクライク複体 (clique complex) は、グラフ内のすべての$k+1$-clique を$k$-simplex と宣言して形成される単純複体である。
我々の主な結果は、重み付きグラフのclique complexが、適当な約束を与えられたとき、$\text{QMA}_1$-hardであり、$\text{QMA}$に含まれるかどうかを決定することである。
我々の主な革新は、組合せラプラシア作用素の固有値を下げる手法である。
このため、スペクトル列として知られる代数的トポロジーからツールを呼び出す。
特にスペクトル列とホッジ理論 [for94] の関係を利用する。
スペクトル列は、組合せラプラシアンの摂動理論に類似した役割を果たす。
また,本研究は,先行研究(CK22)で用いられる外科手術技術を開発した。
この結果は量子tdaアルゴリズム[lgz16]が非量子化できないことを示唆する。
より広い意味では、我々の結果がトポロジカルデータ分析における量子優位の新たな可能性を開くことを望んでいる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。