論文の概要: The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: A Typical Case
- arxiv url: http://arxiv.org/abs/2004.09002v1
- Date: Mon, 20 Apr 2020 00:48:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 23:02:34.239599
- Title: The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: A Typical Case
- Title（参考訳）: 量子近似最適化アルゴリズムは、グラフ全体を見る必要がある:典型的なケース
- Authors: Edward Farhi, David Gamarnik, Sam Gutmann
- Abstract要約: 量子回路は、グラフの局所性を尊重するユニタリ作用素の p 個の応用を持つ。
我々は、d と n を大きく保った dn/2 エッジを持つランダムグラフにおいて、大きな独立集合を見つけることに集中する。
- 参考スコア（独自算出の注目度）: 6.810856082577402
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Quantum Approximate Optimization Algorithm can naturally be applied to
combinatorial search problems on graphs. The quantum circuit has p applications
of a unitary operator that respects the locality of the graph. On a graph with
bounded degree, with p small enough, measurements of distant qubits in the
state output by the QAOA give uncorrelated results. We focus on finding big
independent sets in random graphs with dn/2 edges keeping d fixed and n large.
Using the Overlap Gap Property of almost optimal independent sets in random
graphs, and the locality of the QAOA, we are able to show that if p is less
than a d-dependent constant times log n, the QAOA cannot do better than finding
an independent set of size .854 times the optimal for d large. Because the
logarithm is slowly growing, even at one million qubits we can only show that
the algorithm is blocked if p is in single digits. At higher p the algorithm
"sees" the whole graph and we have no indication that performance is limited.
- Abstract（参考訳）: 量子近似最適化アルゴリズムはグラフ上の組合せ探索問題に自然に適用できる。
量子回路は、グラフの局所性に関するユニタリ作用素のp応用を持つ。
有界次数 p のグラフ上では、QAOA によって出力される状態における遠い量子ビットの測定は、相関しない結果を与える。
我々は、dn/2 辺が d と n を固定するランダムグラフにおける大きな独立集合を見つけることに集中する。
ランダムグラフにおけるほぼ最適な独立集合のオーバーラップギャップ特性と QAOA の局所性を用いて、p が d 依存定数時間log n より小さい場合、QAOA は d 大に対して最適な独立な集合 .854 倍の独立集合を見つけるのに勝ることができないことを示すことができる。
対数の増大は緩やかであり、100万キュービットであっても、pが1桁のときのみアルゴリズムがブロックされていることを示すことができる。
高いpでは、アルゴリズムはグラフ全体を「見る」ので、パフォーマンスが制限されているという兆候はありません。
関連論文リスト
- Quantum Approximate Optimization Algorithms for Maxmimum Cut on Low-Girth Graphs [26.8902894372334]
量子コンピューティングにおいて、Farhi、Gutmann、GoldstoneはMaxCutの問題を解決するためにQuantum Approximate Optimization Algorithm (QAOA)を提案した。
本稿では、加法積グラフとして知られるMohantyとO'Donnellによって提案された拡張グラフの集合上で、MaxCutにQAOAを適用する。
論文 参考訳（メタデータ） (2024-10-06T08:57:30Z) - Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
ランダム正則グラフ上での最大カットと最大独立集合問題を考える。
高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。
両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
論文 参考訳（メタデータ） (2024-06-20T18:00:02Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Graph decomposition techniques for solving combinatorial optimization
problems with variational quantum algorithms [1.2622634782102324]
我々はQAOA入力問題グラフをより小さな問題に分解するアルゴリズムを開発し、削減グラフ上でQAOAを用いてMaxCutを解く。
量子量子コンピュータH1-1上で1層QAOA回路を動作させることにより、10個の100頂点グラフに対する最適解を測定することができる。
論文 参考訳（メタデータ） (2023-06-01T09:44:17Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Quantum Algorithm for Approximating Maximum Independent Sets [0.0]
量子非アベリア断熱混合に基づくグラフの最大独立集合を近似する量子アルゴリズムを提案する。
スパースグラフや密度グラフの場合、平均的な量子アルゴリズムは$alpha(G)$と非常に近い大きさの独立した集合を見つけることができる。
論文 参考訳（メタデータ） (2020-05-26T23:55:49Z) - The Quantum Approximate Optimization Algorithm Needs to See the Whole
Graph: Worst Case Examples [6.810856082577402]
量子近似最適化アルゴリズムは、エッジに対応する項の和であるコスト関数を持つグラフ上の探索問題に適用することができる。
我々は、$(d-1)2p nA$ の QAOA が任意の$A1$ に対して、d 大のランダムな d-正規グラフ上の Max-Cut に対して 1/2 の近似比しか達成できないことを示す。
論文 参考訳（メタデータ） (2020-05-18T14:23:09Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。