論文の概要: Warm-starting quantum optimization

• arxiv url: http://arxiv.org/abs/2009.10095v4
• Date: Wed, 16 Jun 2021 16:12:13 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-01 09:15:13.985687
• Title: Warm-starting quantum optimization
• Title（参考訳）: ウォームスタート量子最適化
• Authors: Daniel J. Egger, Jakub Marecek, Stefan Woerner
• Abstract要約: 最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。 これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。 同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
• 参考スコア（独自算出の注目度）: 6.832341432995627
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
• Abstract（参考訳）: 整数プログラミングと組合せ最適化の問題に対する量子アルゴリズムへの関心が高まっている。 このような問題に対する古典的な解法は、例えば高次元行列値問題(半無限計画法)の形で、バイナリ変数を連続変数に置き換える緩和を用いる。 ユニークなゲーム予想の下では、これらの緩和はしばしば多項式時間で古典的に利用可能な最高のパフォーマンス比を提供する。 本稿では、組合せ最適化問題の緩和解に対応する初期状態で量子最適化を温める方法と、関連する量子アルゴリズムの特性を解析する方法について議論する。 特に、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。 我々は, ポートフォリオ最適化の文脈において, 量子近似最適化アルゴリズム(qaoa)のウォームスタートが低深さでは特に有益であることを示す。 同様に、MAXCUT問題に対する帰納的QAOAは、ゴーマンス・ウィリアムソンのランダム化ラウンドリングが温かいスタートで利用されるとき、ランダムな重み付き完全連結グラフに対するカットの体系的な増加を示す。 同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational Quantum Systems [65.268245109828]
  古典学のパフォーマンスを、半ランダム化された一連のタスクで比較する。 量子システムにおける一般に好適な性能とクエリ効率のため、局所ゼロ階数に着目する。
  論文  参考訳（メタデータ） (2023-10-14T02:13:26Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。 この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。 我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
  論文  参考訳（メタデータ） (2023-06-15T15:28:12Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  本研究では,最適化のための量子および古典的手法の可能性を統合する。 線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。 実量子ハードウェアの計算結果を多数提示する。
  論文  参考訳（メタデータ） (2023-02-10T20:12:53Z)
• Ising formulation of integer optimization problems for utilizing quantum annealing in iterative improvement strategy [1.14219428942199]
  繰り返し改善戦略において量子アニーリングを利用するために,整数最適化問題のイジング定式化を提案する。 基底状態と候補解との重なりがしきい値を超えた場合, 完全に連結されたフェロポッツモデルに対して一階相転移を回避できることを解析的に示す。
  論文  参考訳（メタデータ） (2022-11-08T02:12:49Z)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  現在の量子最適化アルゴリズムでは、元の問題を二進最適化問題として表現し、量子デバイスに適した等価イジングモデルに変換する必要がある。 目的関数を計算し、制約を認証するための古典的プログラムを設計し、後に量子回路にコンパイルする。 その結果,量子近似最適化アルゴリズム (QAOA) が新たに導入された。
  論文  参考訳（メタデータ） (2022-09-07T18:01:01Z)
• Classically-Boosted Quantum Optimization Algorithm [0.0]
  我々は、量子最適化を強化するために既存の古典的手法を活用する自然なアプローチを探求する。 具体的には、近似解を見つけるために古典的なアルゴリズムを実行し、量子回路を用いて高品質な解の「近傍」を探索する。 CBQOA の Max 3SAT および Max Bisection への応用を実証し,これらの問題に対する従来のアプローチよりも優れていることを示す実証的証拠を提供する。
  論文  参考訳（メタデータ） (2022-03-25T23:36:14Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Progress towards analytically optimal angles in quantum approximate optimisation [0.0]
  量子近似最適化アルゴリズム(Quantum Approximate optimization algorithm)は、量子プロセッサ上で実行される時間可変分割演算子である。 p=1$層の最適パラメータが1自由変数に減少し、熱力学の極限で最適角度を回復することが証明された。 さらに、重なり関数の勾配の消失条件は、回路パラメータ間の線形関係を導出し、キュービット数に依存しない類似の形式を持つことを示した。
  論文  参考訳（メタデータ） (2021-09-23T18:00:13Z)
• 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)

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

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