論文の概要: New Approaches to Complexity via Quantum Graphs

• arxiv url: http://arxiv.org/abs/2309.12887v2
• Date: Thu, 23 Jan 2025 19:08:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-27 14:54:17.907266
• Title: New Approaches to Complexity via Quantum Graphs
• Title（参考訳）: 量子グラフによる複雑性の新しいアプローチ
• Authors: Eric Culf, Arthur Mehta,
• Abstract要約: 量子グラフに対するclique問題を紹介し,研究する。 我々のアプローチは量子グラフと量子チャネルの間のよく知られた接続を利用する。 全てのチャネルで量子化され、QMA(2)ではこの問題が完備であることを示す。 また、QMA(k) を QMA(2) に減少させる新たな証拠を与える。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Problems based on the structure of graphs -- for example finding cliques, independent sets, or colourings -- are of fundamental importance in classical complexity. Defining well-formulated decision problems for quantum graphs, which are an operator system generalisation of graphs, presents several technical challenges. Consequently, the connections between quantum graphs and complexity have been underexplored. In this work, we introduce and study the clique problem for quantum graphs. Our approach utilizes a well-known connection between quantum graphs and quantum channels. The inputs for our problems are presented as circuits inducing quantum channel, which implicitly determine a corresponding quantum graph. We show that, quantified over all channels, this problem is complete for QMA(2); in fact, it remains QMA(2)-complete when restricted to channels that are probabilistic mixtures of entanglement-breaking and partial trace channels. Quantified over a subset of entanglement-breaking channels, this problem becomes QMA-complete, and restricting further to deterministic or classical noisy channels gives rise to complete problems for NP and MA, respectively. In this way, we exhibit a classical complexity problem whose natural quantisation is QMA(2), rather than QMA, and provide the first problem that allows for a direct comparison of the classes QMA(2), QMA, MA, and NP by quantifying over increasingly larger families of instances. We use methods that are inspired by self-testing to provide a direct proof of QMA(2)-completeness, rather than reducing to a previously-studied complete problem. We also give a new proof of the celebrated reduction of QMA(k) to QMA(2). In parallel, we study a version of the closely-related independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case.
• Abstract（参考訳）: グラフの構造に基づく問題(例えば、傾き、独立集合、色付けなど)は、古典的な複雑性において基本的な重要性である。 グラフの演算系一般化である量子グラフに対するよく定式化された決定問題を定義することは、いくつかの技術的課題を提起する。 その結果、量子グラフと複雑性の間の関係は過小評価されている。 本研究では,量子グラフの傾き問題を紹介し,研究する。 我々のアプローチは量子グラフと量子チャネルの間のよく知られた接続を利用する。 我々の問題に対する入力は量子チャネルを誘導する回路として示され、それに対応する量子グラフを暗黙的に決定する。 全てのチャネルで定量化されているこの問題は、QMA(2)では完備であり、実際には、絡み込みと部分的トレースチャネルの確率的混合であるチャネルに制限された場合、QMA(2)-完備である。 絡み合うチャネルのサブセット上で量子化され、この問題はQMA完全となり、決定論的または古典的なノイズチャネルにさらに制限されることで、それぞれNPとMAの完全な問題が発生する。 このようにして、自然量子化がQMAではなくQMA(2)である古典的複雑性問題を示し、より大きいインスタンスの族を定量化することによって、クラスQMA(2)、QMA、MA、NPを直接比較できる最初の問題を与える。 我々は、以前に研究された完全問題に還元するのではなく、自己検査にインスパイアされた手法を用いて、QMA(2)完全性の直接的な証明を提供する。 また、QMA(k) を QMA(2) に減少させる新たな証拠を与える。 平行して、量子グラフの密接に関連する独立集合問題のバージョンを研究し、古典的な場合とは対照的に、一般に複雑性が弱くなるという予備的な証拠を提供する。

関連論文リスト

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。 複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。 我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
  論文  参考訳（メタデータ） (2024-11-06T07:29:52Z)
• Many-body quantum resources of graph states [0.0]
  複素多体系の非古典的相関を特徴づけることは量子技術の重要な部分である。 我々は、辺を持つ星グラフ状態、ターアングラフ、$r$ary木グラフ、および正方形格子クラスタ状態の4つの位相を考える。 グラフ状態における多体絡み合う深さは、局所変換やグラフ同型では同値でない146$クラスの最大8$ qubitsで特徴づける。
  論文  参考訳（メタデータ） (2024-10-16T12:05:19Z)
• Quantum property testing in sparse directed graphs [0.9624643581968987]
  古典的な一方向モデルでは、$k$-star-freeness、より一般に$k$-source-subgraph-freenessをテストするという問題は、大きめの$k$にとってほとんど極端に難しい。 量子的にも線形なクエリ数が必要であることも示しています。
  論文  参考訳（メタデータ） (2024-10-07T13:00:43Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
  計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。 複雑性は量子複雑性クラスによって特徴づけられる。 我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
  論文  参考訳（メタデータ） (2023-11-28T21:15:30Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• QuanGCN: Noise-Adaptive Training for Robust Quantum Graph Convolutional Networks [124.7972093110732]
  本稿では,ノード間の局所的なメッセージパッシングをクロスゲート量子演算のシーケンスで学習する量子グラフ畳み込みネットワーク(QuanGCN)を提案する。 現代の量子デバイスから固有のノイズを緩和するために、ノードの接続をスパーズするためにスパース制約を適用します。 我々のQuanGCNは、いくつかのベンチマークグラフデータセットの古典的なアルゴリズムよりも機能的に同等か、さらに優れている。
  論文  参考訳（メタデータ） (2022-11-09T21:43:16Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  まず、量子力学とグラフ理論の相関関係について、量子コンピュータが有用な解を生成できることを示す。 本稿では,その実践性と適用性について,一般的なグラフ学習手法について概説する。 今後の研究の触媒として期待される量子グラフ学習のスナップショットを提供する。
  論文  参考訳（メタデータ） (2022-02-19T02:56:47Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)

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

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