論文の概要: A Quantum-Classical Hybrid Branch & Bound Algorithm
- arxiv url: http://arxiv.org/abs/2511.19501v1
- Date: Sun, 23 Nov 2025 17:44:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-26 17:37:04.049889
- Title: A Quantum-Classical Hybrid Branch & Bound Algorithm
- Title（参考訳）: 量子古典ハイブリッド分岐境界アルゴリズム
- Authors: András Czégel, Dávid Sipos, Boglárka G. -Tóth,
- Abstract要約: 等式制約のある線形プログラムを解くために,完全量子古典ハイブリッド分岐結合アルゴリズム(QCBB)を提案する。
設定されたパーティショニング問題インスタンスについて数値的な結果を示し、アルゴリズムの異なるステップの特徴について多くの詳細を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We propose a complete quantum-classical hybrid branch-and-bound algorithm (QCBB) to solve binary linear programs with equality constraints. That includes bound calculation, convergence metrics and optimality guarantee to the quantum optimization based algorithm, which makes our method directly comparable to classical methods. Key aspects of the proposed algorithm are (i) encapsulation of the quantum optimization method, (ii) utilization of noisy samples for problem reduction, (iii) classical approximation based bound calculation, (iv) branch and bound traits like gap-based stopping criterion and monotonic increase in solution quality, (v) integrated composition of many different solutions that can be improved individually. We show numerical results on set partitioning problem instances and provide many details about the characteristics of the different steps of the algorithm.
- Abstract（参考訳）: 等式制約のある線形プログラムを解くために,完全量子古典ハイブリッド分岐結合アルゴリズム(QCBB)を提案する。
これには、量子最適化に基づくアルゴリズムに対する有界計算、収束測度、最適性保証が含まれており、これは我々の手法を古典的手法と直接比較するものである。
提案アルゴリズムの主な特徴は
(i)量子最適化法のカプセル化
二 ノイズサンプルの問題点低減に利用すること。
三 古典近似に基づく有界計算
(4) ギャップベースの停止基準やモノトニックな溶液品質向上のような分岐および束縛特性。
(v) 個別に改善できる多くの異なる解の統合構成。
設定されたパーティショニング問題インスタンスについて数値的な結果を示し、アルゴリズムの異なるステップの特徴について多くの詳細を提供する。
関連論文リスト
- A Simplification Method for Inequality Constraints in Integer Binary Encoding HOBO Formulations [0.0]
提案手法は,擬似非拘束バイナリ最適化(QUBO)の定式化に伴う課題に対処する。
制約を効率的に統合することにより、量子および古典的解法の計算効率と精度を高めることができる。
論文 参考訳（メタデータ） (2025-01-16T17:06:25Z) - 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) - Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
本稿では,ラグランジアン双対性の概念を断熱量子計算の枠組みに組み込むことにより,制約付き最適化問題の解法を提案する。
回路モデル-フォールトトレラント量子計算の設定において、本手法が回路深さの2次改善を実現し、制約非依存の回路幅を維持することを実証する。
論文 参考訳（メタデータ） (2023-10-06T19:09:55Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。
我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。
これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文 参考訳（メタデータ） (2022-04-07T00:11:05Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳（メタデータ） (2021-11-29T15:10:09Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Quantum approximate algorithm for NP optimization problems with
constraints [12.294570891467604]
本稿では,異なる制約型を等式,線形不等式,任意の形式に定式化する。
そこで本研究では,NP最適化問題の解法としてQAOAフレームワークに適合する制約符号化方式を提案する。
提案手法の有効性と有効性を示す。
論文 参考訳（メタデータ） (2020-02-01T04:45:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。