論文の概要: 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) に減少させる新たな証拠を与える。 平行して、量子グラフの密接に関連する独立集合問題のバージョンを研究し、古典的な場合とは対照的に、一般に複雑性が弱くなるという予備的な証拠を提供する。

関連論文リスト

• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Quantum Computational Complexity and Symmetry [3.481985817302898]
  量子状態とチャネルの対称性をテストすることは、それらの有用性を評価する方法を提供する。 BQP, QMA, QSZK, QIP(2), QIP_EB(2), QIPに対して, 種々の対称性試験問題が完備であることを示す。 また、QMAとQAMに2つのハミルトン対称性試験問題を含むことを証明した。
  論文  参考訳（メタデータ） (2023-09-18T18:48:44Z)
• Quantum Annealing Learning Search Implementations [0.0]
  本稿では、D-Wave量子アニール上でのQALS(Quantum Annealing Learning Search)とQALS(Quantum Annealing Learning Search)の2つの実装の詳細と試験について述べる。
  論文  参考訳（メタデータ） (2022-12-21T15:57:16Z)
• 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)
• Clique Homology is QMA1-hard [0.0]
  simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。 これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。 本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
  論文  参考訳（メタデータ） (2022-09-23T18:14:16Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  量子回路ボルンマシン(QCBM)と量子生成逆ネットワーク(QGAN)の学習可能性について検討する。 まず、QCBMの一般化能力を解析し、量子デバイスがターゲット分布に直接アクセスできる際の優位性を同定する。 次に、QGANの一般化誤差境界が、採用されるAnsatz、クォーディットの数、入力状態に依存することを示す。
  論文  参考訳（メタデータ） (2022-05-10T08:05:59Z)
• BILP-Q: Quantum Coalition Structure Generation [0.0]
  我々は、結合構造生成問題(CSGP)を解決するための最初の一般量子アプローチであるBILP-Qを提案する。 実量子アニール(D-Wave)を用いた中規模問題に対するBILP-Qの実行
  論文  参考訳（メタデータ） (2022-04-28T22:19:50Z)
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity [0.0]
  確率分布から独立したサンプルを描画することはモンテカルロアルゴリズム、機械学習、統計物理学における重要な計算問題である。 この問題は原則として、確率分布全体を符号化した量子状態を作成し、続いて射影測定を行うことで、量子コンピュータ上で解決することができる。 本研究では,イジング連鎖,異なるグラフ上のハードスフィアモデル,非構造探索問題を符号化したモデルなど,様々なモデルのギブス分布に対して,そのような量子状態の漸近的準備の複雑さについて検討する。
  論文  参考訳（メタデータ） (2021-09-07T11:43:45Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  パウリの誤差は、多数の現実的な量子チャネルの中で最も低いサンプリングオーバーヘッドをもたらすことを示す。 我々はQEMと量子チャネル符号化を併用する手法を考案し、純粋なQEMと比較してサンプリングオーバーヘッドの低減を解析する。
  論文  参考訳（メタデータ） (2020-12-15T15:51:27Z)

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

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