論文の概要: Measurements Number Scaling in the Quantum Approximate Optimization Algorithm for MaxCut: A Statistical Analysis
- arxiv url: http://arxiv.org/abs/2607.03340v1
- Date: Fri, 03 Jul 2026 13:57:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-07 22:26:29.594892
- Title: Measurements Number Scaling in the Quantum Approximate Optimization Algorithm for MaxCut: A Statistical Analysis
- Title（参考訳）: MaxCutの量子近似最適化アルゴリズムにおける数スケーリングの測定:統計的解析
- Abstract要約: コスト演算子評価あたりのショット数について十分な条件を導出する: (a) 予測コストを相対誤差$$と信頼度$1-$の範囲内で推定し、(b) パラメータ最適化が高い確率で目標の相対的最適度レベルに収束することを保証する。
本分析は, グラフクラスを形式的に特徴付ける場合, インスタンスサイズが大きくなるにつれて, 固定された相対性能測定値を達成するために必要な全ショット予算が減少する,という予期せぬスケーリング現象を明らかにした。
この結果は、パラメータ最適化冗長性に関する初期のコスト関数集中論を補完し、高性能で低オーバーヘッドなQAOAの可能性を強調する。
- 参考スコア（独自算出の注目度）: 3.0344469521198003
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide a statistical analysis of the measurement (shot) requirements of the quantum approximate optimization algorithm (QAOA) for the MaxCut problem. We derive sufficient conditions on the number of shots per cost operator evaluation to: (a) estimate the expected cost to within a relative error $δ$ and a confidence $1-ε$, and (b) ensure SGD-based parameter optimization converges to a target relative suboptimality level with high probability. In addition, we provide an explicit bound on the number of SGD iterations required to reach the target accuracy. Our analysis reveals an unexpected scaling phenomenon: for specific graph classes, which we formally characterize, the total shot budget needed to achieve a fixed relative-performance metric decreases as the instance size grows. This result complements earlier cost function concentration arguments regarding parameter optimization redundancy, thereby highlighting the potential for high-performance, low-overhead QAOA implementations for large-scale MaxCut instances. To assist practitioners, we translate our analytical findings into practical rules of thumb for shot-budget allocation and validate these results with numerical simulations, offering new insights into the interplay between graph size, structural complexity, and resource requirements in QAOA.
- Abstract（参考訳）: MaxCut問題に対する量子近似最適化アルゴリズム(QAOA)の測定(ショット)要求の統計的解析を行う。
コスト演算子評価におけるショット数に関する十分な条件を導出する。
(a) 予測コストを相対誤差δ$と信頼度1-ε$の範囲内で推定し、
(b)SGDに基づくパラメータ最適化が、高い確率で目標の相対的最適度レベルに収束することを保証する。
さらに、目標精度に到達するのに必要なSGDイテレーションの数を明示的に制限する。
本分析は, グラフクラスを形式的に特徴付ける場合, インスタンスサイズが大きくなるにつれて, 固定された相対性能測定値を達成するために必要な全ショット予算が減少する,という予期せぬスケーリング現象を明らかにした。
この結果は、パラメータ最適化冗長性に関する初期のコスト関数集中論を補完し、大規模MaxCutインスタンスに対する高性能で低オーバーヘッドなQAOA実装の可能性を強調する。
実践者を支援するため,我々は,分析結果を実例に翻訳し,これらの結果を数値シミュレーションで検証し,グラフサイズ,構造複雑性,QAOAにおける資源要件の相互作用に関する新たな洞察を提供する。
関連論文リスト
- Efficiently Estimating Optimal Hyperparameter Scaling Laws through Power-Law Entropy Search [51.33002870475756]
マルチフィデリティベイズ最適化に基づくコスト認識獲得関数である Power-Law Entropy Search (PLES) を導入する。
PLESは、単一の目的関数を最適化するのではなく、スケーリング法見積の全体的な不確実性を低減する候補を検索する。
論文 参考訳（メタデータ） (2026-09-01T15:41:59Z) - EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
既存の技術は情報損失のコストで量子ビットの削減に依存しており、計算性能は劣化している。
等価保存量子ビット効率QAOAを提案し、性能を劣化させることなく必要なキュービット数を著しく削減する。
完全独立変数を持つ非制約問題を除いて,大規模最適化問題に広く適用可能であることを示す。
論文 参考訳（メタデータ） (2026-04-20T13:57:49Z) - QAOA-Predictor: Forecasting Success Probabilities and Minimal Depths for Efficient Fixed-Parameter Optimization [0.9558392439655014]
本稿では,グラフニューラルネットワーク(GNN)を用いた量子近似最適化アルゴリズム(QAOA)の性能予測手法を提案する。
我々は,GNNが真値の10%のマージンでQAOA性能を正確に予測できることを実証した。
論文 参考訳（メタデータ） (2026-03-03T13:43:44Z) - "Over-optimizing" for Normality: Budget-constrained Uncertainty Quantification for Contextual Decision-making [1.2997358113120427]
重み付きサンプル平均近似(wSAA)を用いた文脈最適化の不確実性定量化について検討する。
我々は、wSAAの中央極限定理を確立し、最適条件予測コストに対するアルゴリズム正規性に基づく信頼区間を構築する。
我々は、予算制約付き推定器の収束率をわずかに低下させ、過度に最適化する'(命名規則よりも多くのイテレーションを実行する)が、この過ちを軽減し、正規性を保っていることを示す。
論文 参考訳（メタデータ） (2025-03-17T02:31:56Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - High-dimensional Contextual Bandit Problem without Sparsity [11.287482309003334]
我々は、高次元線形文脈バンドイット問題において、$p$の数は予算$T$よりも大きいか、あるいは無限であるかもしれない。
本稿では,この問題に対処し,その性能を検証するための探索列コミット(EtC)アルゴリズムを提案する。
本稿では,最適バランスを適応的に求める適応探索定理 (AEtC) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-19T15:29:32Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Stochastic Gradient Line Bayesian Optimization: Reducing Measurement
Shots in Optimizing Parameterized Quantum Circuits [4.94950858749529]
我々は、少ない測定ショットで回路最適化を行うための効率的なフレームワークを開発する。
我々は、正確な期待値推定に頼ることなく、最適化を実現するための適応的な計測ショット戦略を定式化する。
本稿では,VQAsの最適化において,接尾辞平均化手法が統計的およびハードウェアノイズの影響を著しく低減できることを示す。
論文 参考訳（メタデータ） (2021-11-15T18:00:14Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。
また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
パフォーマンスバウンダリの定量化は、QAOAが現実のアプリケーションの解決に有効である可能性についての洞察を提供する。
QAOA は、ほとんどのグラフに対して有界な Goemans-Williamson 近似比を超える。
得られたデータセットは、QAOAパフォーマンスに関する経験的バウンダリを確立するためのベンチマークとして提示される。
論文 参考訳（メタデータ） (2021-02-12T23:12:09Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳（メタデータ） (2020-11-05T08:04:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。