論文の概要: Solving General QUBOs with Warm-Start QAOA via a Reduction to Max-Cut
- arxiv url: http://arxiv.org/abs/2504.06253v1
- Date: Tue, 08 Apr 2025 17:57:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-09 13:28:15.608973
- Title: Solving General QUBOs with Warm-Start QAOA via a Reduction to Max-Cut
- Title（参考訳）: ワームスターQAOAによる一般QUBOの解法
- Authors: Bikrant Bhattachayra, Michael Capriotti, Reuben Tate,
- Abstract要約: 古典的な解や情報を用いて初期量子状態を構築する様々な方法を検討する。
Max-Cut問題に対して、1つのウォームスタートアプローチは、対応するMax-Cut問題のSDP緩和から出力される高次元ベクトルを用いて初期状態を構築する。
ウォームスタートアプローチの最良の選択は、問題の種類に強く依存していることが分かりました。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm that finds approximate solutions to problems in combinatorial optimization, especially those that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. In prior work, researchers have considered various ways of "warm-starting" QAOA by constructing an initial quantum state using classically-obtained solutions or information; these warm-starts typically cause QAOA to yield better approximation ratios at much lower circuit depths. For the Max-Cut problem, one warm-start approaches constructs the initial state using the high-dimensional vectors that are output from an SDP relaxation of the corresponding Max-Cut problem. This work leverages these semidefinite warmstarts for a broader class of problem instances by using a standard reduction that transforms any QUBO instance into a Max-Cut instance. We empirically compare this approach to a "QUBO-relaxation" approach that relaxes the QUBO directly. Our results consider a variety of QUBO instances ranging from randomly generated QUBOs to QUBOs corresponding to specific problems such as the traveling salesman problem, maximum independent set, and portfolio optimization. We find that the best choice of warmstart approach is strongly dependent on the problem type.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、組合せ最適化における問題の近似解を求める量子アルゴリズムである。
これまでの研究で研究者は、古典的に観測された解や情報を用いて初期量子状態を構築することで、QAOAの「ウォームスタート」の様々な方法を検討してきた。
Max-Cut問題に対して、1つのウォームスタートアプローチは、対応するMax-Cut問題のSDP緩和から出力される高次元ベクトルを用いて初期状態を構築する。
この研究は、任意のQUBOインスタンスをMax-Cutインスタンスに変換する標準還元を用いることで、これらの半定温開始をより広範な問題インスタンスのクラスに活用する。
このアプローチを,QUBOを直接緩和する "QUBO-relaxation" アプローチと実証的に比較する。
本研究は,QUBOインスタンスをランダムに生成したQUBOから,旅行セールスマン問題,最大独立セット,ポートフォリオ最適化といった特定の問題に対応するQUBOインスタンスについて検討した。
ウォームスタートアプローチの最良の選択は、問題の種類に強く依存していることが分かりました。
関連論文リスト
- A hybrid classical-quantum approach to highly constrained Unit Commitment problems [0.0]
単位コミットメント(UC)問題は、電力産業における重要な最適化課題である。
本稿では,UC問題を時間内に効率的に解くために,新しいハイブリッド量子古典アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-12-15T21:21:36Z) - Warm-Started QAOA with Aligned Mixers Converges Slowly Near the Poles of the Bloch Sphere [0.0]
研究者は古典的なアルゴリズムから返された解を利用して、QAOAのためのウォームスタートした量子初期状態を作り出した。
小さい$theta$の場合、回路深さの低い境界は、$Delta lambda/theta$とほぼ比例する。
論文 参考訳（メタデータ） (2024-09-16T14:43:42Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Systematic study on the dependence of the warm-start quantum approximate
optimization algorithm on approximate solutions [0.0]
近似解の精度がウォームスタートQAOA(WS-QAOA)の性能に与える影響について検討する。
WS-QAOAは、ハミング距離の観点から、近似解が正確な解に近づくにつれてQAOAを上回る傾向にある。
また、QAOAを介して得られる近似解を用いてWS-QAOAによるMAX-CUT問題を解く。
論文 参考訳（メタデータ） (2022-09-07T05:26:48Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Classically-Boosted Quantum Optimization Algorithm [0.0]
我々は、量子最適化を強化するために既存の古典的手法を活用する自然なアプローチを探求する。
具体的には、近似解を見つけるために古典的なアルゴリズムを実行し、量子回路を用いて高品質な解の「近傍」を探索する。
CBQOA の Max 3SAT および Max Bisection への応用を実証し,これらの問題に対する従来のアプローチよりも優れていることを示す実証的証拠を提供する。
論文 参考訳（メタデータ） (2022-03-25T23:36:14Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Warm-starting quantum optimization [6.832341432995627]
最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。
これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。
同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
論文 参考訳（メタデータ） (2020-09-21T18:00:09Z) - 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) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。