論文の概要: On the Role of Problem Structure in Single-Layer QAOA

• arxiv url: http://arxiv.org/abs/2610.30511v1
• Date: Wed, 21 Oct 2026 22:41:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-24 02:08:44.170191
• Title: On the Role of Problem Structure in Single-Layer QAOA
• Title（参考訳）: 単層QAOAにおける問題構造の役割について
• Abstract要約: 単一層QAOAにおける目標状態振幅の観点から問題構造を捉える数学的対象を同定する。 この構造は計算基底の特異な粗い分割によって誘導される結合確率分布に符号化されていることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Problem structure is regarded as a key factor influencing the performance of the Quantum Approximate Optimization Algorithm (QAOA), yet it remains an informal notion without a precise mathematical characterization. In this work, we address this issue by identifying a mathematical object that captures problem structure as seen from the perspective of the target state amplitude in single-layer QAOA. Specifically, we show that this structure is encoded in a joint probability distribution induced by the unique coarsest partition of the computational basis, determined by problem cost values and mixer-dependent walk counts. The statistical dependence between these classes provides a means of quantifying the available problem structure and identifying necessary conditions for exponential amplification. To assess the extent to which this structure can translate into algorithmic performance, we establish a mean-max non-separation bound relating the parameter-averaged probability of measuring the target configuration to its variational maximum. For NPO-PB problems with polynomially many distinct mixer eigenvalues, these probabilities exhibit the same scaling up to polynomial factors. This allows us to characterize the exponential scaling of optimal amplitude amplification by analyzing the parameter-averaged probability without explicitly optimizing the variational parameters. We then derive an exact expression for the parameter-averaged probability as a matrix inner product involving two objects that separately encode the joint structural distribution and the mixer dynamics. This representation provides a framework for identifying the structural mechanisms governing the amplification of the target-state probability or its exponential suppression relative to the mixer capacity. We demonstrate these mechanisms through analytically tractable examples involving transverse field and Grover mixers.
• Abstract（参考訳）: 問題構造は量子近似最適化アルゴリズム(QAOA)の性能に影響を与える重要な要因と考えられているが、正確な数学的特徴を持たない非公式な概念である。 本研究では,単一層QAOAにおける目標状態振幅の観点から問題構造を捉える数学的対象を特定することにより,この問題に対処する。 具体的には,この構造は,問題コスト値とミキサー依存歩行数によって決定された,計算ベースにおける一意な粗い分割によって誘導される結合確率分布に符号化されていることを示す。 これらのクラス間の統計的依存は、利用可能な問題構造を定量化し、指数的増幅に必要な条件を特定する手段を提供する。 この構造がアルゴリズム性能に変換できる範囲を評価するために、ターゲット構成をその変動最大値に測定するパラメータ平均確率に関する平均非分離境界を確立する。 多項式的に多くの異なるミキサー固有値を持つ NPO-PB 問題に対して、これらの確率は多項式因子まで同じスケーリングを示す。 これにより、変動パラメータを明示的に最適化することなく、パラメータ平均化確率を解析することにより、最適振幅増幅の指数的スケーリングを特徴付けることができる。 次に、パラメータ平均確率の正確な式を、結合構造分布とミキサー力学を別々に符号化する2つの対象を含む行列内積として導出する。 この表現は、ターゲット状態確率の増幅またはミキサー容量に対する指数的抑制を規定する構造機構を識別するための枠組みを提供する。 本研究では, これらのメカニズムを, 逆場とグローバーミキサーを含む解析的抽出可能な例を通して実証する。

関連論文リスト

• Avoided-crossings, degeneracies and Berry phases in the spectrum of quantum noise through analytic Bloch-Messiah decomposition [49.1574468325115]
  解析的ブロッホ・メシア分解 (analytic Bloch-Messiah decomposition) は量子光学系の力学を特徴づけるためのアプローチを提供する。 単一パラメータが変化した場合,回避された交差は自然に発生し,特異ベクトルの過敏性をもたらすことを示す。 我々は,避けられた交差を意図的に設計することで,フォトニックシステムのスペクトル応答をプログラムできる可能性を強調した。
  論文  参考訳（メタデータ） (2025-04-29T13:14:15Z)
• Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz [3.5023108034606256]
  QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための量子アルゴリズムの一分野である。 特定の変種であるGrover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA)は、等価な目的値を共有する状態間で均一な振幅を保証する。 GM-QAOAはサンプリング確率を2次的に向上させ,一貫した性能を維持するために,問題サイズと指数関数的にスケールする回路深度を必要とすることを示す。
  論文  参考訳（メタデータ） (2024-05-06T05:47:27Z)
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer [0.0]
  本稿では,問題ハミルトニアンスペクトルに付随する確率分布に依存する予測値の解析式として,GM-QAOAを統計的に解析する手法を提案する。 我々はこの分析を、Grover-based QAOAと呼ぶGrovermixerを用いて、より一般的なQAOAの文脈に拡張する。
  論文  参考訳（メタデータ） (2024-01-19T23:17:08Z)
• A Robustness Analysis of Blind Source Separation [91.3755431537592]
  ブラインドソース分離(BSS)は、変換$f$が可逆であるが未知であるという条件の下で、その混合である$X=f(S)$から観測されていない信号を復元することを目的としている。 このような違反を分析し、その影響を$X$から$S$のブラインドリカバリに与える影響を定量化するための一般的なフレームワークを提案する。 定義された構造的仮定からの偏差に対する一般的なBSS溶出は、明示的な連続性保証という形で、利益的に分析可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-17T16:30:51Z)
• Distribution Regression with Sliced Wasserstein Kernels [45.916342378789174]
  分布回帰のための最初のOTに基づく推定器を提案する。 このような表現に基づくカーネルリッジ回帰推定器の理論的性質について検討する。
  論文  参考訳（メタデータ） (2022-02-08T15:21:56Z)
• Probabilistic Simplex Component Analysis [66.30587591100566]
  PRISMは、データ循環記述のシンプルさの頂点をデータから識別する確率論的シンプルコンポーネント分析手法である。 この問題には多様な応用があり、最も注目すべきはリモートセンシングにおけるハイパースペクトルアンミックスと機械学習における非負行列分解である。
  論文  参考訳（メタデータ） (2021-03-18T05:39:00Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  [1]では、ランダムに投影された線形判別式のアンサンブルを用いてデータセットを分類する。 我々は,計算コストのかかるクロスバリデーション推定器の代替として,誤分類確率の一貫した推定器を開発する。 また、実データと合成データの両方で投影次元を調整するための推定器の使用を実証する。
  論文  参考訳（メタデータ） (2020-04-17T12:47:04Z)

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

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