論文の概要: Clique Homology is QMA1-hard
- arxiv url: http://arxiv.org/abs/2209.11793v1
- Date: Fri, 23 Sep 2022 18:14:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-25 09:58:13.061751
- Title: Clique Homology is QMA1-hard
- Title(参考訳): Clique Homology は QMA1-hard である
- Authors: Marcos Crichigno and Tamara Kohler
- Abstract要約: simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。
これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。
本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We tackle the long-standing question of the computational complexity of
determining homology groups of simplicial complexes, a fundamental task in
computational topology, posed by Kaibel and Pfetsch 20 years ago. We show that
this decision problem is QMA1-hard. Moreover, we show that a version of the
problem satisfying a suitable promise and certain constraints is contained in
QMA. This suggests that the seemingly classical problem may in fact be quantum
mechanical. In fact, we are able to significantly strengthen this by showing
that the problem remains QMA1-hard in the case of clique complexes, a family of
simplicial complexes specified by a graph which is relevant to the problem of
topological data analysis. The proof combines a number of techniques from
Hamiltonian complexity and homological algebra. We discuss potential
implications for the problem of quantum advantage in topological data analysis.
- Abstract(参考訳): 20年前にkaibel と pfetsch が提唱した計算トポロジーの基本課題である単純複体のホモロジー群を決定する計算複雑性に関する長年の疑問に挑戦する。
この決定問題はQMA1-hardである。
さらに,問題のバージョンが適切な約束を満足し,一定の制約がQMAに含まれることを示す。
これは、一見古典的な問題は実際には量子力学であることを示唆している。
実際、この問題は、トポロジカルデータ解析の問題に関連するグラフによって定義された単体錯体の族であるクリッド錯体の場合、QMA1-ハードのままであることを示すことで、これを著しく強化することができる。
この証明はハミルトン複雑性とホモロジー代数の多くの技法を組み合わせたものである。
トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
関連論文リスト
- Promise Clique Homology on weighted graphs is $\text{QMA}_1$-hard and
contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
この結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文 参考訳(メタデータ) (2023-11-28T21:15:30Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳(メタデータ) (2023-10-04T17:53:55Z) - New Approaches to Complexity via Quantum Graphs [0.0]
量子グラフに対するclique問題を紹介し,研究する。
我々の問題に対する入力は、回路によって誘導される量子チャネルとして表現される。
言語内のチャネルのコレクションを変更することで、これらがクラス$textsfNP$, $textsfMA$, $textsfQMA$, $textsfQMA(2)$の完全な問題を引き起こします。
論文 参考訳(メタデータ) (2023-09-22T14:20:14Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳(メタデータ) (2022-09-28T17:53:25Z) - Quantum Parameterized Complexity [1.01129133945787]
パラメータ化複雑性クラスの範囲の量子アナログを導入する。
このフレームワークは、QMAハード問題のパラメータ化バージョンの複雑さの豊富な分類を公開している。
論文 参考訳(メタデータ) (2022-03-15T15:34:38Z) - Simultaneous Stoquasticity [0.0]
確率ハミルトニアンは、局所ハミルトニアン問題の計算複雑性において重要な役割を果たしている。
2つ以上のハミルトニアンがユニタリ変換によって同時に確率的になるかどうかという問題に対処する。
論文 参考訳(メタデータ) (2022-02-17T19:08:30Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳(メタデータ) (2022-01-06T03:10:53Z) - Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
我々は、$mathcal N=2 $ 超対称性を持つフェルミオンハミルトニアンの文脈における局所ハミルトニアン問題の複雑さを考える。
これを研究する主な動機は、超対称系の基底状態エネルギーがちょうどゼロであることと、あるコホモロジー群が非自明であることである。
論文 参考訳(メタデータ) (2021-06-30T18:00:01Z) - Quantum-optimal-control-inspired ansatz for variational quantum
algorithms [105.54048699217668]
変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。
ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。
この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
論文 参考訳(メタデータ) (2020-08-03T18:00:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。