論文の概要: Per-Shot Evaluation of QAOA on Max-Cut: A Black-Box Implementation Comparison with Goemans-Williamson

• arxiv url: http://arxiv.org/abs/2604.08367v1
• Date: Thu, 09 Apr 2026 15:33:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-10 18:34:05.997146
• Title: Per-Shot Evaluation of QAOA on Max-Cut: A Black-Box Implementation Comparison with Goemans-Williamson
• Title（参考訳）: Max-Cut上でのQAOAのショット当たり評価: Goemans-Williamsonによるブラックボックス実装の比較
• Authors: Evgenii Dolzhkov, Franz G. Fuchs, Dirk Oliver Theis,
• Abstract要約: The Quantum Approximate Optimization Algorithm (QAOA) on the Max-Cut problem。 多くの先行研究とは異なり、本手法はQAOAの実装をブラックボックスとして扱う。 分析の中心的なコンポーネントは、QAOA出力の品質を追跡するショットごとの統計フレームワークである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for addressing combinatorial optimization problems on near-term quantum hardware. In this work, we conduct an empirical evaluation of QAOA on the Max-Cut problem, using the Goemans-Williamson (GW) algorithm as a classical baseline for comparison. Unlike many prior studies, our methodology treats QAOA implementations as black-box optimizers, relying solely on default parameter settings without manual fine-tuning. We evaluate specific off-the-shelf QAOA implementations under default settings, not the algorithmic potential of QAOA with optimized parameters. This reflects a more realistic use case for end users who may lack the resources or expertise for instance-specific optimization. To facilitate fair and informative evaluation, we construct benchmark instances using well-known graph generation models that emulate practical graph structures, avoiding synthetic constructions tailored to either quantum or classical algorithms. A central component of our analysis is a per-shot statistical framework, which tracks the quality of QAOA outputs as a function of the number of circuit executions. This enables probabilistic comparisons with the GW algorithm by examining when and how frequently QAOA surpasses classical performance baselines such as the GW expectation and lower bound. Our results provide insight into the practical applicability of QAOA for Max-Cut and highlight its current limitations, offering a framework that can guide the assessment and development of future QAOA implementations.
• Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は、短期量子ハードウェアにおける組合せ最適化問題に対処するための有望なアプローチとして登場した。 本稿では,GWアルゴリズムを古典的ベースラインとして用いて,Max-Cut問題に対するQAOAの実証評価を行う。 多くの先行研究とは異なり、本手法は手作業による微調整なしにデフォルトパラメータ設定のみに依存するブラックボックスオプティマイザとしてQAOAの実装を扱う。 最適化されたパラメータを持つQAOAのアルゴリズム的ポテンシャルではなく,既定設定下での市販QAOAの実装を評価する。 これは、インスタンス固有の最適化のためのリソースや専門知識が欠けているエンドユーザにとって、より現実的なユースケースを反映しています。 公正かつ情報的な評価を容易にするため、実用的なグラフ構造をエミュレートするよく知られたグラフ生成モデルを用いてベンチマークインスタンスを構築し、量子アルゴリズムや古典アルゴリズムに適した合成構成を避ける。 分析の中心となるのは、QAOA出力の質を回路実行回数の関数として追跡する、ショットごとの統計フレームワークである。 これにより、QAOAがGW期待値や下限値といった古典的なパフォーマンスベースラインを超える頻度と頻度を調べることで、GWアルゴリズムとの確率的比較が可能になる。 この結果から,Max-Cut におけるQAOA の実用性に関する知見が得られ,その限界を浮き彫りにし,今後のQAOA 実装の評価と開発をガイドするフレームワークを提供する。

関連論文リスト

• Adam assisted Fully informed Particle Swarm Optimization ( Adam-FIPSO ) based Parameter Prediction for the Quantum Approximate Optimization Algorithm (QAOA) [1.024113475677323]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、マックス・カット問題などの最適化問題の解法として用いられる顕著な変分アルゴリズムである。 QAOAの重要な課題は、高品質なソリューションにつながる適切なパラメータを効率的に特定することである。
  論文  参考訳（メタデータ） (2025-06-07T13:14:41Z)
• A hybrid quantum-classical approach to warm-starting optimization [0.0]
  ポートフォリオ最適化の観点から,標準QAOAとウォームスタートQAOAのパフォーマンスを比較した。 この結果が,従来の問題に先行する純粋に古典的な前処理によって再現されるか,あるいは超えられることを示し,その後に標準的なQAOAが続く。
  論文  参考訳（メタデータ） (2023-09-25T08:53:54Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。 この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。 我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
  論文  参考訳（メタデータ） (2023-06-15T15:28:12Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Trusted-Maximizers Entropy Search for Efficient Bayesian Optimization [39.824086260578646]
  本稿では,信頼度最大化エントロピー探索(TES)取得関数を提案する。 インプットがクエリの情報ゲインにどの程度貢献するかを、信頼された最大値の有限セット上で測定する。
  論文  参考訳（メタデータ） (2021-07-30T07:25:07Z)
• Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
  パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。 QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。 得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
  論文  参考訳（メタデータ） (2021-02-12T23:12:09Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Evaluation of QAOA based on the approximation ratio of individual samples [0.0]
  我々は、Max-Cut問題に適用されたQAOAの性能をシミュレートし、いくつかの古典的代替品と比較する。 QAOA計算複雑性理論のガイダンスが進化しているため、量子的優位性を求めるためのフレームワークを利用する。
  論文  参考訳（メタデータ） (2020-06-08T18:00:18Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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