論文の概要: Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz
- arxiv url: http://arxiv.org/abs/2405.04303v3
- Date: Tue, 08 Apr 2025 02:46:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-09 13:26:17.398698
- 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要約: そこで本研究では,QAOA+アンサッツを用いたPQA(Progressive Quantum Algorithm)を提案する。
PQAはキュービットの5.565%$(2.170%$)とランタイムの17.59%$(6.430%$)しか必要としない。
- 参考スコア（独自算出の注目度）: 7.693541968022234
- License:
- Abstract: Hadfield et al. proposed a novel Quantum Alternating Operator Ansatz algorithm (QAOA+), and this algorithm has wide applications in solving constrained combinatorial optimization problems (CCOPs) because of the advantages of QAOA+ ansatz in constructing a feasible solution space. In this paper, we propose a Progressive Quantum Algorithm (PQA) with QAOA+ ansatz to solve the Maximum Independent Set (MIS) problem using fewer qubits. The core idea of PQA is to construct a subgraph that is likely to contain the MIS solution of the target graph and then solve the MIS problem on this subgraph to obtain an approximate solution. To construct such a subgraph, PQA starts with a small-scale initial subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results demonstrate that to achieve an approximation ratio of 0.95, PQA requires only $5.565\%$ ($2.170\%$) of the qubits and $17.59\%$ ($6.430\%$) of the runtime compared with directly solving the original problem using QAOA+ on Erd\H{o}s-R\'enyi (3-regular) graphs, highlighting the efficiency of PQA.
- Abstract（参考訳）: Hadfieldらは、量子交互演算子アンザッツアルゴリズム(QAOA+)を提案し、このアルゴリズムは、実現可能な解空間を構築する際のQAOA+アンザッツの利点から、制約付き組合せ最適化問題(CCOP)の解法に広く応用されている。
本稿では,QAOA+アンサッツを用いたPQA(Progressive Quantum Algorithm)を提案する。
PQAの中核となる考え方は、対象グラフのMIS解を含む可能性のある部分グラフを構築し、この部分グラフ上のMIS問題を解いて近似解を得ることである。
このような部分グラフを構築するために、PQAは小規模な初期部分グラフから始まり、ヒューリスティック展開戦略を用いてグラフサイズを徐々に拡大する。
各展開後、PQAは新たに生成された部分グラフ上でMIS問題を解く。
各ランにおいて、PQAは、予め定義された停止状態に到達するまで拡張と解決のプロセスを繰り返す。
シミュレーションの結果、近似比が 0.95 に達するためには、PQA はキュービットの 5.565 %$ (2.170 %$) とランタイムの $17.59 %$ (6.430 %$) しか必要とせず、Erd\H{o}s-R\enyi (3-regular) グラフ上の QAOA+ を直接解いて PQA の効率を強調している。
関連論文リスト
- An Adaptive Mixer Allocation Algorithm for the Quantum Alternating Operator Ansatz [2.7704630812545474]
制約付き最適化問題の解法としてアダプティブミキサーアロケーションアルゴリズム(AMA)を提案する。
AMAはリソース消費を大幅に減らし、QAOA+の回路深度は34.08%$29.77%、CNOTゲートの数は15.05%$18.72%である。
論文 参考訳（メタデータ） (2024-12-27T12:43:36Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。