論文の概要: Progressive Quantum Algorithm for Quantum Alternating Operator Ansatz
- arxiv url: http://arxiv.org/abs/2405.04303v1
- Date: Tue, 7 May 2024 13:26:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-08 14:00:34.891573
- Title: Progressive Quantum Algorithm for Quantum Alternating Operator Ansatz
- Title（参考訳）: 量子交互演算子アンザッツのプログレッシブ量子アルゴリズム
- Authors: Xiao-Hui Ni, Yan-Qi Song, Ling-Xiao Li, Su-Juan Qin, Fei Gao, Qiao-Yan Wen,
- Abstract要約: 我々は、量子交換演算子Ansatz(QAOA+)のリソースオーバーヘッドを軽減するために、PQA(Progressive Quantum Algorithm)と呼ばれるアプローチを導入する。
PQAは、QAOA+を同じレベルの深さ$p$で直接解決するのと比較して、平均近似比(AAR)と重要な量子資源の節約を示す。
- 参考スコア（独自算出の注目度）: 7.746319535055413
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, Hadfield has proposed a novel Quantum Alternating Operator Ansatz (QAOA+) to tackle Constrained Combinatorial Optimization Problems (CCOPs), and it has wide applications. However, the large requirement of multi-qubit controlled gates in QAOA+ limits its applications in solving larger-scale CCOPs. To mitigate the resources overhead of QAOA+, we introduce an approach termed Progressive Quantum Algorithm (PQA). In this paper, the concept and performance of PQA are introduced focusing on the Maximal Independent Set (MIS) problem. PQA aims to yield the solution of the target graph $G$ with fewer resources by solving the MIS problem on a desired derived subgraph that has the same MIS solution as $G$ but has a much smaller graph size. To construct such a desired subgraph, PQA gradually and regularly expands the graph size starting from a well-designed initial subgraph. After each expansion, PQA solves the MIS problem on the current subgraph using QAOA+ and estimates whether the current graph has the same MIS solution as the target graph. PQA repeats the graph expansion and solving process until reaching the stop condition. In our simulations, the performance of PQA is benchmarked on Erd\H{o}s-R\'enyi (ER) and regular graphs. The simulation results suggest that PQA showcases higher average approximation ratio (AAR) and significant quantum resource savings compared with directly solves the original problem using QAOA+ (DS-QAOA+) at the same level depth $p$. Remarkably, the AAR obtained by PQA is $12.9305\%$ ($4.8645\%$) higher than DS-QAOA+ on ER (regular) graphs, and the average number of multi-qubit gates (qubits) consumed by PQA is 1/3 (1/2) of that of DS-QAOA+. The remarkable efficiency of PQA makes it possible to solve larger-scale CCOPs on the current quantum devices.
- Abstract（参考訳）: 近年、Hadfield は Constrained Combinatorial Optimization Problems (CCOPs) に取り組むための新しいQuantum Alternating Operator Ansatz (QAOA+) を提案しており、幅広い応用がある。
しかし、QAOA+におけるマルチキュービット制御ゲートの大きな要求は、大規模CCOPの解決における応用を制限する。
本稿では,QAOA+のリソースオーバーヘッドを軽減するために,PQA(Progressive Quantum Algorithm)というアプローチを導入する。
本稿では,PQAの概念と性能を最大独立集合問題(MIS)に焦点をあてて紹介する。
PQA は、目的とするグラフの解を、より少ないリソースで$G$ とし、より小さいグラフサイズで$G$ と同じ MIS 解を持つ所望の導出部分グラフ上の MIS 問題を解くことを目的としている。
このような望まれる部分グラフを構築するために、PQAは、よく設計された初期部分グラフから始まるグラフサイズを徐々に、定期的に拡大する。
各拡張の後、PQAはQAOA+を用いて現在のサブグラフ上のMIS問題を解き、現在のグラフがターゲットグラフと同じMIS解を持つかどうかを推定する。
PQAは停止状態に到達するまでグラフの拡大と解法を繰り返す。
シミュレーションでは,Erd\H{o}s-R\enyi (ER) および正規グラフ上でPQAの性能をベンチマークした。
シミュレーションの結果,PQAは,QAOA+(DS-QAOA+)と同等の深さで,QAOA+(DS-QAOA+)と直接的に比較すると,平均近似比(AAR)と有意な量子資源貯蓄を示すことが示唆された。
PQAが取得したAARは、ERグラフ上のDS-QAOA+よりも12.9305\%$(4.8645\%$)高く、PQAが消費するマルチキュービットゲート(キュービット)の平均数はDS-QAOA+の1/3(1/2)である。
PQAの顕著な効率は、現在の量子デバイス上での大規模CCOPの解決を可能にする。
関連論文リスト
- Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
本稿では,新しいQAOAアンサッツについて述べる。
我々は、新しいアンザッツの一般式を$p=1$で導き、サイクルグラフの近似比の改善を解析的に示す。
論文 参考訳（メタデータ） (2024-11-07T22:20:01Z) - Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、MAX-CUT問題などの最適化問題を概ね解くことを目的として提案された量子古典ハイブリッドアルゴリズムである。
まず、二部グラフ上のMAX-CUT問題の解法におけるレベル1QAOAの性能限界を解析的に証明する。
第2に、再帰的QAOA(RQAOA)は、QAOAをサブルーチンとしてグラフサイズを削減し、レベル1のQAOAを上回る性能を示す。
最後に,制限パラメータを持つRQAOAが,これらの制約に完全に対処可能であることを示す。
論文 参考訳（メタデータ） (2024-08-23T16:35:47Z) - Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games [3.6021182997326022]
100%再生可能エネルギーへの移行には、マイクログレードと呼ばれる有能なプロシューマーのサブセットに分割するなど、エネルギーネットワークを管理する新しい技術が必要である。
最適な方法で行うことは、誘導サブグラフゲームにおける結合構造生成問題に抽象化できるため、難しい最適化問題である。
本研究は,GCS-Qをソリューション品質の面で上回りうるかどうかを検証し,より控えめなQAベースのアプローチを提案する。
論文 参考訳（メタデータ） (2024-08-08T10:54:56Z) - Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
そこで本研究では,MaxCut問題のスケーラブルな解に対するQAOA2法の実装について述べる。
The limit of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA。
最大33量子ビットの大規模シミュレーションの結果は、ある場合におけるQAOAの利点と実装の効率性を示す。
論文 参考訳（メタデータ） (2024-06-25T09:02:31Z) - 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) - Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
我々はPolyak-Ruppert 平均 Q-leaning (平均 Q-leaning) を用いた同期 Q-learning を$gamma$-discounted MDP で検討した。
繰り返し平均$barboldsymbolQ_T$に対して正規性を確立する。
要するに、我々の理論分析は、Q-Leaningの平均は統計的に効率的であることを示している。
論文 参考訳（メタデータ） (2021-12-29T14:47:56Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。