論文の概要: The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization

• arxiv url: http://arxiv.org/abs/2505.18396v2
• Date: Mon, 09 Jun 2025 20:49:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-11 15:11:40.067622
• Title: The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Title（参考訳）: XY-mixerトポロジーのリー代数と制約最適化のためのウォームスタートQAOA
• Authors: Steven Kordonowy, Hannes Leipold,
• Abstract要約: XYミキサーは、変分量子アルゴリズムを含む現代の量子コンピューティングで広く利用されている。 我々は、様々な$XY$-mixer位相に付随する動的リー代数の明示的な分解を与える。 我々はこれらの概念をPortfolio Optimization, Sparsest $k$-Subgraph, Graphing で示す数値シミュレーションを行った。
• 参考スコア（独自算出の注目度）: 0.9208007322096533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The XY-mixer has widespread utilization in modern quantum computing, including in variational quantum algorithms, such as Quantum Alternating Operator Ansatz (QAOA). The XY ansatz is particularly useful for solving Cardinality Constrained Optimization tasks, a large class of important NP-hard problems. First, we give explicit decompositions of the dynamical Lie algebras (DLAs) associated with a variety of $XY$-mixer topologies. When these DLAs admit simple Lie algebra decompositions, they are efficiently trainable. An example of this scenario is a ring $XY$-mixer with arbitrary $R_Z$ gates. Conversely, when we allow for all-to-all $XY$-mixers or include $R_{ZZ}$ gates, the DLAs grow exponentially and are no longer efficiently trainable. We provide numerical simulations showcasing these concepts on Portfolio Optimization, Sparsest $k$-Subgraph, and Graph Partitioning problems. These problems correspond to exponentially-large DLAs and we are able to warm-start these optimizations by pre-training on polynomial-sized DLAs by restricting the gate generators. This results in improved convergence to high quality optima of the original task, providing dramatic performance benefits in terms of solution sampling and approximation ratio on optimization tasks for both shared angle and multi-angle QAOA.
• Abstract（参考訳）: XY-mixerは、量子交互演算子Ansatz (QAOA)のような変分量子アルゴリズムを含む、現代の量子コンピューティングにおいて広く利用されている。 XYアンザッツは、重要なNPハード問題の大規模なクラスであるCardinality Constrained Optimizationタスクを解くのに特に有用である。 まず、様々な$XY$-mixer位相に付随する動的リー代数(DLAs)の明示的な分解を与える。 これらの DLA が単純リー代数分解を許すとき、それらは効率的に訓練可能である。 このシナリオの例として、任意の$R_Z$ゲートを持つリング$XY$-mixerがある。 逆に、すべての$XY$-mixersを許可したり、$R_{ZZ}$ gatesを含ませる場合、DLAは指数関数的に成長し、もはや効率的に訓練できない。 我々はこれらの概念をPortfolio Optimization, Sparsest $k$-Subgraph, Graph Partitioningで示す数値シミュレーションを行った。 これらの問題は指数関数的に大きいDLAに対応しており、ゲートジェネレータを制限して多項式サイズのDLAを事前学習することで、これらの最適化をウォームスタートすることができる。 これにより、元のタスクの高品質な最適化への収束性が向上し、共有角度と多角QAOAの両方の最適化タスクにおける解サンプリングと近似比の点で劇的な性能上の利点が得られる。

関連論文リスト

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• On the dynamical Lie algebras of quantum approximate optimization algorithms [4.987686869768721]
  動的リー代数(DLAs)は、パラメータ化量子回路の研究において貴重な道具として登場した。 本研究では,量子近似最適化アルゴリズム(QAOA)のDLAについて検討する。 DLAの次元が$O(n3)$であることを示し、DLAの明示的な基底を与える。
  論文  参考訳（メタデータ） (2024-07-17T14:12:30Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  本稿では,分散学習における部分トラグラーの緩和を目的とした,新たな勾配符号化方式を提案する。 L の符号パラメータを L に表わした勾配座標符号化方式を提案する。
  論文  参考訳（メタデータ） (2022-06-06T09:25:40Z)
• How Much Entanglement Do Quantum Optimization Algorithms Require? [0.0]
  ADAPT-QAOA施行時に発生する絡みについて検討した。 この柔軟性を漸進的に制限することにより、初期におけるより多くの絡み合いエントロピーが、後段におけるより速い収束と一致していることが分かる。
  論文  参考訳（メタデータ） (2022-05-24T18:00:02Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。 我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。 我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
  論文  参考訳（メタデータ） (2022-03-11T17:19:26Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit [0.05076419064097732]
  推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。 この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
  論文  参考訳（メタデータ） (2021-10-20T17:58:53Z)
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation [0.0]
  本稿では,Grover 様選択位相シフト混合演算子を用いた量子交互演算子 Ansatz (QAOA) の変種を提案する。 GM-QAOA は任意のNP最適化問題に取り組み、全ての実現可能な解の同値な重ね合わせを効率的に作成することができる。
  論文  参考訳（メタデータ） (2020-05-30T20:24:53Z)

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

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