論文の概要: 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)$への還元の新たな証明を含む。
また,量子グラフの独立集合問題の複雑性についても検討し,クランク問題と独立集合問題とが等価である古典的な場合とは対照的に,複雑性が一般に弱いという予備的な証拠を与える。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。