論文の概要: 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) - 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) - QSETH strikes again: finer quantum lower bounds for lattice problem,
strong simulation, hitting set problem, and more [5.69353915790503]
現在の量子ハードウェアでは「簡単な」計算上の優位性がないという問題がある。
量子コンピュータ上でこれらの問題を解くのが難しいという証拠を得たいのですが、その正確な複雑さは何でしょうか?
QSETHフレームワーク [Buhrman-Patro-Speelman 2021] を用いることで、CNFSATのいくつかの自然変種の量子複雑性を理解することができる。
論文 参考訳(メタデータ) (2023-09-28T13:30:20Z) - 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) - Spectral bounds for the quantum chromatic number of quantum graphs [0.0]
量子隣接行列の固有値を用いて量子グラフの古典的および量子的数に対する下界を求める。
エルフィックとウォクジャンによって与えられる全てのスペクトル境界を量子グラフ設定に一般化する。
この結果は線形代数の手法と量子グラフカラー化の完全定義を用いて達成される。
論文 参考訳(メタデータ) (2021-12-03T05:36:21Z) - Quantum Meets the Minimum Circuit Size Problem [3.199102917243584]
量子環境における最小回路サイズ問題(MCSP)について検討する。
MCSPはブール関数の回路複雑性を計算する問題である。
これらの問題はNPではなくQCMA(あるいはQCMAプロトコル)にあることを示す。
論文 参考訳(メタデータ) (2021-08-06T15:34:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。