論文の概要: ParaQAOA: Efficient Parallel Divide-and-Conquer QAOA for Large-Scale Max-Cut Problems Beyond 10,000 Vertices

• arxiv url: http://arxiv.org/abs/2603.26232v1
• Date: Fri, 27 Mar 2026 09:55:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-30 21:49:48.431097
• Title: ParaQAOA: Efficient Parallel Divide-and-Conquer QAOA for Large-Scale Max-Cut Problems Beyond 10,000 Vertices
• Title（参考訳）: ParaQAOA:10,000頂点を超える大規模マックスカット問題に対する効率的な並列除算およびコンカレントQAOA
• Authors: Po-Hsuan Huang, Xie-Ru Li, Chi Chuang, Chia-Heng Tu, Shih-Hao Hung,
• Abstract要約: ParaQAOA は大規模な Max-Cut 問題に対する並列分割・コンカレントフレームワークである。 最もよく知られた解の2%以内の解精度を維持しつつ、400の頂点を持つMax-Cut問題に対する最先端の手法よりも1,600倍の高速化を実現している。 ParaQAOAは16,000頂点のインスタンスを19分で解決するが、最もよく知られているアプローチでは13.6日以上かかる。
• 参考スコア（独自算出の注目度）: 0.41942958779358674
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising solution for combinatorial optimization problems using a hybrid quantum-classical framework. Among combinatorial optimization problems, the Maximum Cut (Max-Cut) problem is particularly important due to its broad applicability in various domains. While QAOA-based Max-Cut solvers have been developed, they primarily favor solution accuracy over execution efficiency, which significantly limits their practicality for large-scale problems. To address the limitation, we propose ParaQAOA, a parallel divide-and-conquer QAOA framework that leverages parallel computing hardware to efficiently solve large Max-Cut problems. ParaQAOA significantly reduces runtime by partitioning large problems into subproblems and solving them in parallel while preserving solution quality. This design not only scales to graphs with tens of thousands of vertices but also provides tunable control over accuracy-efficiency trade-offs, making ParaQAOA adaptable to diverse performance requirements. Experimental results demonstrate that ParaQAOA achieves up to 1,600x speedup over state-of-the-art methods on Max-Cut problems with 400 vertices while maintaining solution accuracy within 2% of the best-known solutions. Furthermore, ParaQAOA solves a 16,000-vertex instance in 19 minutes, compared to over 13.6 days required by the best-known approach. These findings establish ParaQAOA as a practical and scalable framework for large-scale Max-Cut problems under stringent time constraints.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は,ハイブリッドな量子古典的フレームワークを用いた組合せ最適化問題に対する有望な解法である。 組合せ最適化問題の中で、最大カット(Max-Cut)問題は様々な領域で適用可能であるため特に重要である。 QAOAベースのMax-Cutソルバは開発されているが、それらは実行効率よりも解の精度を優先しており、大規模な問題に対する実用性を著しく制限している。 この制限に対処するため,並列コンピューティングハードウェアを活用する並列分割型QAOAフレームワークであるParaQAOAを提案する。 ParaQAOAは、ソリューションの品質を維持しながら、大きな問題をサブプロブレムに分割し、それらを並列に解決することで、ランタイムを著しく削減します。 この設計は、数万の頂点を持つグラフにスケールするだけでなく、精度と効率のトレードオフを調整可能なコントロールを提供する。 実験の結果,ParaQAOAは最大1,600倍の高速化を実現し,解の精度を最もよく知られた解の2%以内で維持した。 さらに、ParaQAOAは16,000頂点のインスタンスを19分で解決するが、最もよく知られているアプローチでは13.6日以上かかる。 これらの結果から,ParaQAOAは時間制約下での大規模Max-Cut問題に対して,実用的でスケーラブルなフレームワークとして確立された。

関連論文リスト

• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化Ansatzのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 XY$-mixersは検索スペースを制限するため、特定の状態ベクトルエントリは常にゼロであり、シミュレーションから省略することができ、貴重なメモリとコンピューティングリソースを節約できる。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。 完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
  論文  参考訳（メタデータ） (2025-01-02T05:06:16Z)
• QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem [6.783232060611114]
  より大規模なMax-Cut問題を解決するためにQAOA回路を設計するためのフレームワークを提案する。 古典アルゴリズムとQAOAの近似比を仮定して理論的に近似を保証する。 われわれのフレームワークは平均で18ドルと0.950ドルしか消費しない。
  論文  参考訳（メタデータ） (2023-07-28T02:06:42Z)
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management [45.82374977939355]
  本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。 我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。 実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
  論文  参考訳（メタデータ） (2023-02-08T17:09:20Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  余分なスラック変数を必要としない代替手法を提案する。 我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。 この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
  論文  参考訳（メタデータ） (2022-11-25T06:05:18Z)
• 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)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。