論文の概要: Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs

• arxiv url: http://arxiv.org/abs/2609.03317v1
• Date: Thu, 03 Sep 2026 03:12:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-04 18:28:38.900213
• Title: Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs
• Title（参考訳）: 非循環グラフ上でのQAOA表現率の効率的な推定
• Abstract要約: 古典的なグラフ構造を用いて、変分アルゴリズムの量子力学を診断し、潜在的に導く方法を示す。 この結果から,古典的なグラフ構造を用いて量子ハードウェア上で動作させる前に,変分アルゴリズムの量子力学を診断・導出する方法が示唆された。
• 参考スコア（独自算出の注目度）: 0.35398689122254773
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classically equivalent formulations of an optimization problem need not lead to equivalent quantum algorithms. For MaxCut, fixing the value of a single vertex removes a simple global symmetry without changing the underlying optimization problem, yet it can substantially alter the quantum dynamics generated by the Quantum Approximate Optimization Algorithm (QAOA). These dynamics are captured by the circuit's dynamical Lie algebra (DLA), whose direct construction can become exponentially expensive. Here we show that, for symmetry-reduced QAOA on trees, substantial information about the reduced DLA can instead be obtained efficiently from the graph alone. We introduce a polynomial classical algorithm that recursively distinguishes vertices using shortest path structure and degree parity. When all vertices are resolved individually, the method determines the complete reduced DLA and, under the corresponding graph conditions, certifies maximal expressibility of the reduced QAOA ansatz. Even when full resolution is not achieved, the algorithm identifies embedded subalgebras, provides rigorous lower bounds on DLA dimension, and certifies controllable subsystems. Our theoretical and experimental results show how classical graph structure can be used to diagnose and potentially guide the quantum dynamics of variational algorithms before running them on quantum hardware.
• Abstract（参考訳）: 古典的に等価な最適化問題の定式化は等価な量子アルゴリズムに繋がる必要はない。 MaxCut にとって、単一の頂点の値の固定は、基礎となる最適化問題を変更せずに単純な大域対称性を除去するが、量子近似最適化アルゴリズム (QAOA) によって生成される量子力学を実質的に変更することができる。 これらの力学は回路の動的リー代数(DLA)によって捉えられ、直接構成は指数関数的に高価になる。 ここでは、木上の対称性還元QAOAに対して、削減されたDLAに関する実質的な情報を得る代わりに、グラフのみから効率的に得られることを示す。 最短経路構造と次数パリティを用いて頂点を再帰的に区別する多項式古典アルゴリズムを提案する。 全ての頂点が個別に解決されると、この手法は完全な縮小DLAを決定し、対応するグラフ条件の下では、削減されたQAOAアンザッツの最大表現性を証明する。 完全な解像度が達成されていない場合でも、アルゴリズムは組み込みサブ代数を特定し、DLA次元の厳密な下限を提供し、制御可能なサブシステムを証明する。 我々の理論的および実験的結果は、古典グラフ構造が量子ハードウェア上で実行する前に、変分アルゴリズムの量子力学を診断し、ガイドするためにどのように使用できるかを示している。

関連論文リスト

• Emergent Problem-Graph Alignment in RL-Discovered Entanglement Topologies for QAOA [3.03715087930992]
  本稿では,QAOAをベースとしたMaxCut最適化において,問題グラフに直接アクセスすることなく,より効果的な絡み合いトポロジを学習エージェントが発見できるかどうかを検討する。 この結果から,トポロジー密度に支配されるトレーサビリティ-表現トレードオフが明らかとなり,変動最適化のランドスケープがハミルトニアン問題に関する構造情報を暗黙的にエンコードしていることが示唆された。
  論文  参考訳（メタデータ） (2026-08-07T18:17:08Z)
• Multivariate Decoded Quantum Interferometry for Weighted Optimization [6.4675604105664]
  量子干渉法 (Quantum Interferometry, DQI) は、特定のMax-LINSAT問題に対して最もよく知られたアナログ時間古典アルゴリズムに比べて、復号化への離散最適化を低減させる。 元々の定式化において、DQIはすべての制約を均一に扱い、興味のあるほとんどの最適化問題に存在する重み構造を利用できない。
  論文  参考訳（メタデータ） (2026-05-11T14:45:46Z)
• Reductions of QAOA Induced by Classical Symmetries: Theoretical Insights and Practical Implications [0.35398689122254773]
  古典的対称性はQAOAの設計原理として体系的に活用できることを示す。 リー代数の構造は、どの変数が固定されているかによって劇的に変化することを示す。 結果は、表現的でトレーニング可能なQAOA回路を設計するための基本ツールとして、対称性を考慮したリダクションを確立する。
  論文  参考訳（メタデータ） (2026-02-18T02:20:42Z)
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
  連続時間量子ウォーク(CTQW)に基づく最小頂点被覆(MVC)問題に対する新しい量子アルゴリズムを提案する。 この枠組みでは、グラフ上の量子ウォーカーのコヒーレントな伝播は、その構造特性を状態振幅に符号化する。 我々は,CTQWに基づくアルゴリズムが優れた近似比を一貫して達成し,ネットワークトポロジに関して顕著な堅牢性を示すことを示す。
  論文  参考訳（メタデータ） (2025-12-02T17:04:57Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  チュートリアルは変分量子回路とQUBO問題の概要から始まる。 次に、ハミルトンの定式化、ゲート分解、サンプル応用など、QAOAの詳細を探索する。 このチュートリアルはこれらの概念を高階ハミルトニアンに拡張し、関連する対称性と回路構成について議論する。
  論文  参考訳（メタデータ） (2025-11-23T09:54:20Z)
• 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)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  本稿では,QUBO行列におけるテクステミシンメトリの概念を紹介する。 提案アルゴリズムは結合数と回路深さを最大45%削減することを示した。
  論文  参考訳（メタデータ） (2024-12-18T12:05:18Z)
• 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)
• On the dynamical Lie algebras of quantum approximate optimization algorithms [4.987686869768721]
  動的リー代数(DLAs)は、パラメータ化量子回路の研究において貴重な道具として登場した。 本研究では,量子近似最適化アルゴリズム(QAOA)のDLAについて検討する。 DLAの次元が$O(n3)$であることを示し、DLAの明示的な基底を与える。
  論文  参考訳（メタデータ） (2024-07-17T14:12:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。 我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。 すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
  論文  参考訳（メタデータ） (2020-10-01T18:14:11Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)

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

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