論文の概要: 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-18 02:18:13.586743
- 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 の効率を強調している。
関連論文リスト
- 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) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - 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) - Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。
この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。
有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
論文 参考訳（メタデータ） (2022-05-16T15:47:41Z) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - 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) - Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
グラフ最大カット問題(MaxCut)の課題に対処するため,Divide-and-Conquer QAOA(DC-QAOA)を提案する。
DC-QAOAは97.14%の近似比(20.32%)を達成する
また、従来のQAOAの時間的複雑さを指数関数から二次的に減少させる。
論文 参考訳（メタデータ） (2021-02-26T03:10:30Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。