論文の概要: Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
- arxiv url: http://arxiv.org/abs/2308.10765v1
- Date: Mon, 21 Aug 2023 14:53:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-22 13:10:29.569109
- Title: Hybrid Algorithm of Linear Programming Relaxation and Quantum Annealing
- Title(参考訳): 線形計画緩和と量子アニーリングのハイブリッドアルゴリズム
- Authors: Taisei Takabayashi, Masayuki Ohzeki
- Abstract要約: 1つのアプローチは、古典的アルゴリズムを用いて近似解を取得し、量子アニール(QA)を用いてそれを精製することである。
本稿では,リニアプログラミング(LP)緩和と呼ばれる単純な連続緩和手法を用いる手法を提案する。
- 参考スコア(独自算出の注目度): 0.6526824510982802
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The demand for classical-quantum hybrid algorithms to solve large-scale
combinatorial optimization problems using quantum annealing (QA) has increased.
One approach involves obtaining an approximate solution using classical
algorithms and refining it using QA. In previous studies, such variables were
determined using molecular dynamics (MD) as a continuous optimization method.
We propose a method that uses the simple continuous relaxation technique called
linear programming (LP) relaxation. Our method demonstrated superiority through
comparative experiments with the minimum vertex cover problem versus the
previous MD-based approach. Furthermore, the hybrid approach of LP relaxation
and simulated annealing showed advantages in accuracy and speed compared to
solving with simulated annealing alone.
- Abstract(参考訳): 量子アニール(QA)を用いた大規模組合せ最適化問題に対する古典量子ハイブリッドアルゴリズムの需要が高まっている。
1つのアプローチは、古典的アルゴリズムを用いて近似解を取得し、QAを用いてそれを精製することである。
これまでの研究では、分子動力学(md)を連続最適化法として用いた。
本稿では,リニアプログラミング(LP)緩和と呼ばれるシンプルな連続緩和手法を提案する。
提案手法は, 従来のMD法と比較して, 最小頂点被覆問題を用いた比較実験により優位性を示した。
さらに,LP緩和とシミュレートアニールのハイブリッドアプローチは,シミュレートアニール単独による解法と比較して,精度と速度の優位性を示した。
関連論文リスト
- An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳(メタデータ) (2023-06-10T08:25:16Z) - Linear combination of Hamiltonian simulation for nonunitary dynamics
with optimal state preparation cost [8.181184006712785]
ハミルトンシミュレーション問題の線形結合として,非単位力学の一般クラスをシミュレーションする簡単な方法を提案する。
また,全てのパラメータにほぼ最適に依存した複素吸収ポテンシャル法によるオープン量子力学シミュレーションの応用を実証した。
論文 参考訳(メタデータ) (2023-03-02T07:37:54Z) - Computational Complexity of Sub-linear Convergent Algorithms [0.0]
小サンプルから始めて幾何的に拡大し、前のサンプルの解を用いて新しいEMMを計算する方法について検討する。
これにより、線形収束の1次最適化アルゴリズムの問題を解決するが、計算の複雑さは小さくなる。
論文 参考訳(メタデータ) (2022-09-29T05:38:06Z) - A conditional gradient homotopy method with applications to Semidefinite
Programming [1.6369790794838281]
ホモトピーに基づく条件勾配法による凸最適化問題の解法。
我々の理論的複雑さは、最先端のSDPに直面すると競合し、安価なプロジェクションフリーの決定的な利点がある。
論文 参考訳(メタデータ) (2022-07-07T05:48:27Z) - Meta-Learning Digitized-Counterdiabatic Quantum Optimization [3.0638256603183054]
本稿では,リカレントニューラルネットワークを用いたメタラーニング手法を用いて,変分最適化に適した初期パラメータを求める問題に取り組む。
我々は、最近提案されたディジタル化対数量子近似アルゴリズム(DC-QAOA)を用いて、この手法について検討する。
メタラーニングとDC-QAOAを組み合わせることで、MaxCut問題やSherrington-Kirkpatrickモデルなど、異なるモデルに対する最適な初期パラメータを見つけることができる。
論文 参考訳(メタデータ) (2022-06-20T18:57:50Z) - Robust Quantum Control using Hybrid Pulse Engineering [0.0]
勾配に基づく最適化アルゴリズムは、初期推定に対する感度によって制限される。
我々の数値解析は、その収束速度が優れていることを裏付ける。
本稿では,雑音場を組み込んだノイズ耐性量子制御法について述べる。
論文 参考訳(メタデータ) (2021-12-02T14:29:42Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z) - A Dynamical Systems Approach for Convergence of the Bayesian EM
Algorithm [59.99439951055238]
我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。
本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。
高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
論文 参考訳(メタデータ) (2020-06-23T01:34:18Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳(メタデータ) (2020-06-11T18:49:06Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。