論文の概要: Learning Cut Distributions with Quantum Optimization

• arxiv url: http://arxiv.org/abs/2604.14381v1
• Date: Wed, 15 Apr 2026 19:55:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-17 21:29:31.586496
• Title: Learning Cut Distributions with Quantum Optimization
• Title（参考訳）: 量子最適化によるカット分布の学習
• Authors: Bao Bach, Cameron Ibrahim, Reuben Tate, Jad Salem, Stephan Eidenbenz, Ilya Safro,
• Abstract要約: 本稿では,分散最適化問題に対する量子的アプローチを提案する。 有限層の層で、ビットストリング上の任意の分布を捉えるためにQAOAアンサッツを構築することができる。 提案アルゴリズムは,グラフ構造上の古典的近似よりも有意に優れていることを示す。
• 参考スコア（独自算出の注目度）: 0.3113876454957647
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many combinatorial optimization problems admit a maximin fairness variant, where the aim is to find a distribution over possible solutions which maximizes an expected worst-case outcome. However, the support for an optimal distribution may be exponential, which can be intractable to represent in the worst case. To this end, we propose a quantum based approach to solving distribution optimization problems. Expanding on work analyzing the Dynamical Lie Algebras of the Quantum Approximate Optimization Algorithm (QAOA), we show that with a finite number of layers, a QAOA ansatz can be constructed to capture any distribution over bitstrings. We show that the resulting circuit is able to effectively solve the Fair Cut Cover, a fair interpretation of the classical Fractional Cut Cover Problem. In addition, we show that our algorithm is provably better than classical approximations on certain graph structures and empirically outperforms these classical algorithms on tested instances.
• Abstract（参考訳）: 多くの組合せ最適化問題は、期待される最悪の結果を最大化する可能な解上の分布を見つけることを目的として、最大値の変動を許容する。 しかし、最適分布のサポートは指数関数であり、最悪の場合において表現できる。 そこで本研究では,分散最適化問題を解くための量子ベースアプローチを提案する。 量子近似最適化アルゴリズム(QAOA)の動的リー代数解析により,有限層でビットストリング上の任意の分布を捉えるために,QAOAアンサッツを構築することができることを示す。 得られた回路は,古典的切断被覆問題の公平な解釈であるフェアカット被覆を効果的に解くことができることを示す。 さらに,本アルゴリズムは,特定のグラフ構造上の古典的近似よりも有意に優れており,テストインスタンス上でこれらの古典的アルゴリズムよりも経験的に優れていることを示す。

関連論文リスト

• 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)
• 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)
• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。 このアルゴリズムは古典的および量子速度歪み理論に適用できる。
  論文  参考訳（メタデータ） (2024-08-10T06:16:24Z)
• Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems [7.723735038335632]
  量子近似最適化アルゴリズム(QAOA)は、量子超越性を実証するための有望な候補と考えられている。 量子ビットの可用性が制限され、コヒーレンス時間制限がQAOAに挑戦し、大規模な擬ブール問題を解く。 本稿では,これを単純化したIsingモデルに変換することで,一般の擬似ブール問題を解く分散QAOAを提案する。
  論文  参考訳（メタデータ） (2023-10-08T08:07:11Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Quantization-Based Optimization: Alternative Stochastic Approximation of Global Optimization [0.0]
  NP-hard問題における目的関数のエネルギーレベルを定量化するための大域的最適化アルゴリズムを提案する。 数値実験により,提案アルゴリズムはNP-ハード最適化問題の解法において従来の学習法よりも優れていた。
  論文  参考訳（メタデータ） (2022-11-08T03:01:45Z)
• Quantum variational optimization: The role of entanglement and problem hardness [0.0]
  本稿では, 絡み合いの役割, 変動量子回路の構造, 最適化問題の構造について検討する。 数値計算の結果,絡み合うゲートの分布を問題のトポロジに適応させる利点が示唆された。 リスク型コスト関数に条件値を適用することで最適化が向上し、最適解と重複する確率が増大することを示す。
  論文  参考訳（メタデータ） (2021-03-26T14:06:54Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。 本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。 本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-04T00:26:56Z)
• Improving the Quantum Approximate Optimization Algorithm with postselection [0.0]
  組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。 理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-10T22:17:50Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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