論文の概要: Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models
- arxiv url: http://arxiv.org/abs/2204.10306v2
- Date: Wed, 28 Sep 2022 18:29:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-16 03:25:33.367811
- Title: Performance and limitations of the QAOA at constant levels on large
sparse hypergraphs and spin glass models
- Title（参考訳）: 大きなスパースハイパーグラフおよびスピンガラスモデルにおける一定レベルのQAOAの性能と限界
- Authors: Joao Basso, David Gamarnik, Song Mei, Leo Zhou
- Abstract要約: 無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。
我々の分析は、サドル点近似の和対パス積分によって理解することができる。
一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
- 参考スコア（独自算出の注目度）: 15.857373057387669
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a general purpose
quantum algorithm designed for combinatorial optimization. We analyze its
expected performance and prove concentration properties at any constant level
(number of layers) on ensembles of random combinatorial optimization problems
in the infinite size limit. These ensembles include mixed spin models and
Max-$q$-XORSAT on sparse random hypergraphs. Our analysis can be understood via
a saddle-point approximation of a sum-over-paths integral. This is made
rigorous by proving a generalization of the multinomial theorem, which is a
technical result of independent interest. We then show that the performance of
the QAOA at constant levels for the pure $q$-spin model matches asymptotically
the ones for Max-$q$-XORSAT on random sparse Erd\H{o}s-R\'{e}nyi hypergraphs
and every large-girth regular hypergraph. Through this correspondence, we
establish that the average-case value produced by the QAOA at constant levels
is bounded away from optimality for pure $q$-spin models when $q\ge 4$ and is
even. This limitation gives a hardness of approximation result for quantum
algorithms in a new regime where the whole graph is seen.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化のために設計された汎用量子アルゴリズムである。
無限大極限におけるランダムな組合せ最適化問題のアンサンブル上で,期待性能を解析し,任意の一定レベル(層数)で濃度特性を証明した。
これらのアンサンブルには混合スピンモデルとスパースランダムハイパーグラフ上のMax-$q$-XORSATが含まれる。
本解析は,sum-over-paths積分のsaddle-point近似によって解釈できる。
これは独立関心の技術的結果である多項定理の一般化を証明することによって厳密にされる。
すると、純粋な$q$-spinモデルにおけるqaoaの性能は、ランダムなスパース erd\h{o}s-r\'{e}nyiハイパーグラフおよび全ての大域正規ハイパーグラフ上のmax-$q$-xorsatのものと漸近的に一致することを示した。
この対応を通じて、一定のレベルでqaoaによって生成される平均ケース値は、$q\ge 4$かつ偶数である純粋な$q$-spinモデルの最適性から切り離される。
この制限は、グラフ全体が見える新しい状態における量子アルゴリズムの近似結果の難しさを与える。
関連論文リスト
- Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm [0.0]
ランダム正則グラフ上での最大カットと最大独立集合問題を考える。
高い正則性に対してQAOAが達成したエネルギー密度を$d=100$まで計算する。
両問題に対する最適性について,QAOA分析と最先端の上界を結合する。
論文 参考訳（メタデータ） (2024-06-20T18:00:02Z) - The Overlap Gap Property limits limit swapping in QAOA [0.0]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化問題(COP)のために設計された量子アルゴリズムである。
スピンガラス上でのQAOAの性能は, スピンガラスの平均解法における古典的アルゴリズムと同等であることを示す。
論文 参考訳（メタデータ） (2024-04-09T07:45:06Z) - An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文 参考訳（メタデータ） (2023-02-09T07:47:06Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit [0.05076419064097732]
推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。
この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
論文 参考訳（メタデータ） (2021-10-20T17:58:53Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳（メタデータ） (2020-11-16T18:43:09Z) - SGD with shuffling: optimal rates without component convexity and large
epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。
我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。
我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文 参考訳（メタデータ） (2020-06-12T05:00:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。