論文の概要: Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz
- arxiv url: http://arxiv.org/abs/2405.04303v2
- Date: Thu, 26 Sep 2024 09:13:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-09 02:52:29.911041
- Title: Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz
- Title（参考訳）: 量子交互演算子アンザッツを用いた最大独立集合のプログレッシブ量子アルゴリズム
- Authors: Xiao-Hui Ni, Ling-Xiao Li, Yan-Qi Song, Zheng-Ping Jin, Su-Juan Qin, Fei Gao,
- Abstract要約: 本稿では,最大独立集合(MIS)問題を解く上で必要となるキュービットを削減するために,プログレッシブ量子アルゴリズム(PQA)を提案する。
シミュレーションの結果、最適近似比0.95を達成するためには、キュービットの5.5565%$(15.4%$)とランタイムの10.695%$(7.23%$)しか必要としないことがわかった。
- 参考スコア（独自算出の注目度）: 7.693541968022234
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, Hadfield et al. proposed the Quantum Alternating Operator Ansatz (QAOA+) to tackle Constrained Combinatorial Optimization Problems (CCOPs). This paper proposes a Progressive Quantum Algorithm (PQA) to reduce the required qubits in solving the Maximum Independent Set (MIS) problem using QAOA+ ansatz. PQA constructs a subgraph that contains the MIS solution of the target graph $G$ and then solves the MIS problem on this subgraph to obtain the solution for $G$. To induce such a subgraph, PQA starts with a small-scale initial subgraph and progressively expands its graph size utilizing designed expansion rules. After each expansion, PQA solves the MIS problem on the current subgraph using QAOA+. In each run, PQA repeats the graph expansion and solving process until a predefined stopping condition is reached. Simulation results demonstrate that to achieve an optimal approximation ratio of 0.95, PQA requires only $5.5565\%$ ($15.4\%$) of the qubits and $10.695\%$ ($7.23\%$) of the runtime compared with QAOA+ on Erd\H{o}s-R\'enyi (regular) graphs, highlighting the efficiency of PQA.
- Abstract（参考訳）: 近年、Hadfieldらは、Constrained Combinatorial Optimization Problems (CCOPs)に取り組むためにQuantum Alternating Operator Ansatz (QAOA+)を提案した。
本稿では,QAOA+アンサッツを用いた最大独立集合(MIS)問題の解法において,必要量子ビットを削減するためのプログレッシブ量子アルゴリズム(PQA)を提案する。
PQA は対象グラフの MIS 解を$G$ に含んだ部分グラフを構築し、その後、この部分グラフ上の MIS 問題を解いて$G$ の解を得る。
このような部分グラフを誘導するために、PQAは小規模な初期部分グラフから始まり、設計された拡張ルールを利用してグラフのサイズを徐々に拡大する。
各展開の後、PQAはQAOA+を用いて現在の部分グラフ上のMIS問題を解く。
各ランにおいて、PQAは、予め定義された停止条件に到達するまで、グラフの展開と解法を繰り返す。
シミュレーションの結果、最適近似比が 0.95 に達するためには、PQA はキュービットの 5.5565 %$ (15.4 %$) とランタイムの 10.695 %$ (7.23 %$) しか必要とせず、Erd\H{o}s-R\enyi (正規) グラフの QAOA+ と比較すると、PQA の効率を強調している。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。