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

• arxiv url: http://arxiv.org/abs/2309.12887v1
• Date: Fri, 22 Sep 2023 14:20:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-25 14:20:59.547895
• Title: New Approaches to Complexity via Quantum Graphs
• Title（参考訳）: 量子グラフによる複雑性の新しいアプローチ
• Authors: Eric Culf and Arthur Mehta
• Abstract要約: 量子グラフに対するclique問題を紹介し,研究する。 我々の問題に対する入力は、回路によって誘導される量子チャネルとして表現される。 言語内のチャネルのコレクションを変更することで、これらがクラス$textsfNP$, $textsfMA$, $textsfQMA$, $textsfQMA(2)$の完全な問題を引き起こします。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Problems based on the structure of graphs -- for example finding cliques, independent sets, or colourings -- are of fundamental importance in classical complexity. It is well motivated to consider similar problems about quantum graphs, which are an operator system generalisation of graphs. Defining well-formulated decision problems for quantum graphs faces several technical challenges, and 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 quantum channels induced by circuits, which implicitly determine a corresponding quantum graph. We also use this approach to reimagine the clique and independent set problems for classical graphs, by taking the inputs to be circuits of deterministic or noisy channels which implicitly determine confusability graphs. We show that, by varying the collection of channels in the language, these give rise to complete problems for the classes $\textsf{NP}$, $\textsf{MA}$, $\textsf{QMA}$, and $\textsf{QMA}(2)$. In this way, we exhibit a classical complexity problem whose natural quantisation is $\textsf{QMA}(2)$, rather than $\textsf{QMA}$, which is commonly assumed. To prove the results in the quantum case, we make use of methods inspired by self-testing. To illustrate the utility of our techniques, we include a new proof of the reduction of $\textsf{QMA}(k)$ to $\textsf{QMA}(2)$ via cliques for quantum graphs. We also study the complexity of a version of the independent set problem for quantum graphs, and provide preliminary evidence that it may be in general weaker in complexity, contrasting to the classical case where the clique and independent set problems are equivalent.
• Abstract（参考訳）: グラフの構造に基づく問題(例えば、クランク、独立集合、彩色など)は、古典的複雑性において重要な問題である。 グラフの作用素系一般化である量子グラフに関する同様の問題を考える動機は十分にある。 量子グラフに対するよく定式化された決定問題の定義はいくつかの技術的課題に直面しており、量子グラフと複雑性の関連性は過小評価されている。 本研究では,量子グラフの傾き問題を紹介し,研究する。 この手法は量子グラフと量子チャネル間のよく知られた接続を利用する。 この問題の入力は回路によって誘導される量子チャネルとして提示され、対応する量子グラフを暗黙的に決定する。 また、この手法を用いて、古典グラフの斜めおよび独立な集合問題を再定義し、その入力を可算性グラフを暗黙的に決定する決定的あるいはノイズの多いチャネルの回路とする。 言語内のチャネルのコレクションを変更することで、これらはクラス$\textsf{NP}$, $\textsf{MA}$, $\textsf{QMA}$, $\textsf{QMA}(2)$の完全な問題を引き起こす。 このようにして、自然量子化が一般に仮定される$\textsf{qma}$ではなく$\textsf{qma}(2)$である古典的な複雑性問題を示す。 量子の場合の結果を証明するために、自己検査にインスパイアされた手法を用いる。 この手法の有用性を説明するために、量子グラフのクリックスによる$\textsf{QMA}(k)$から$\textsf{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)

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

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