論文の概要: Ising Hamiltonians for Constrained Combinatorial Optimization Problems
and the Metropolis-Hastings Warm-Starting Algorithm
- arxiv url: http://arxiv.org/abs/2307.08980v1
- Date: Tue, 18 Jul 2023 05:28:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-19 16:19:41.695147
- Title: Ising Hamiltonians for Constrained Combinatorial Optimization Problems
and the Metropolis-Hastings Warm-Starting Algorithm
- Title（参考訳）: 制約付き組合せ最適化問題とメトロポリス・ハスティングス・ウォームスターティングアルゴリズムのためのハミルトニアン
- Authors: Hui-Min Li, Jin-Min Liang, Zhi-Xi Wang, Shao-Ming Fei
- Abstract要約: 量子近似最適化アルゴリズム(QAOA)は最適化問題に対する有望な変分量子アルゴリズムである。
QAOAのMetropolis-Hasstingウォームスタートアルゴリズムは、大域的最適解に確実に収束することができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum approximate optimization algorithm (QAOA) is a promising variational
quantum algorithm for combinatorial optimization problems. However, the
implementation of QAOA is limited due to the requirement that the problems be
mapped to Ising Hamiltonians and the nonconvex optimization landscapes.
Although the Ising Hamiltonians for many NP hard problems have been obtained, a
general method to obtain the Ising Hamiltonians for constrained combinatorial
optimization problems (CCOPs) has not yet been investigated. In this paper, a
general method is introduced to obtain the Ising Hamiltonians for CCOPs and the
Metropolis-Hastings warm-starting algorithm for QAOA is presented which can
provably converge to the global optimal solutions. The effectiveness of this
method is demonstrated by tackling the minimum weight vertex cover (MWVC)
problem, the minimum vertex cover (MVC) problem, and the maximal independent
set problem as examples. The Ising Hamiltonian for the MWVC problem is obtained
first time by using this method. The advantages of the Metropolis-Hastings
warm-starting algorithm presented here is numerically analyzed through solving
30 randomly generated MVC cases with 1-depth QAOA.
- Abstract（参考訳）: 量子近似最適化アルゴリズム(QAOA)は組合せ最適化問題に対する有望な変分量子アルゴリズムである。
しかしながら、qaoaの実装はイジングハミルトニアンと非凸最適化のランドスケープに問題をマッピングする必要性から制限されている。
多くのNP問題に対するIsing Hamiltonianが得られたが、制約付き組合せ最適化問題(CCOP)に対するIsing Hamiltoniansを得る一般的な方法はまだ研究されていない。
本稿では,ccopsのためのイジングハミルトニアンを得るための一般的な方法を紹介し,大域的最適解に確実に収束可能なqaoaのためのメトロポリス・ハスティングスウォームスタートアルゴリズムを提案する。
本手法の有効性は, 最小ウェイト頂点被覆(MWVC)問題, 最小バーテックス被覆(MVC)問題, 最大独立集合問題を例に挙げて示す。
MWVC問題に対するIsing Hamiltonianは、この方法を用いて初めて得られる。
ここで提示されるMetropolis-Hastingsウォームスタートアルゴリズムの利点は、ランダムに生成された30のMVCケースを1-depth 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) - Symmetries and Dimension Reduction in Quantum Approximate Optimization
Algorithm [1.3469999282609788]
我々は、$n-要素$d$-ary文字列の集合上で定義される最適化問題の一般化された定式化に焦点を当てる。
我々の主な貢献は、当初提案されたQAOAの次元を含む。
アルゴリズムをより小さな次元の空間に制限することは、回路の量子シミュレーションと古典シミュレーションの両方を著しく加速させる可能性がある。
論文 参考訳（メタデータ） (2023-09-25T00:35:40Z) - 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) - Iterative Quantum Optimization with Adaptive Problem Hamiltonian [19.4417702222583]
このような制限された問題で得られた解をハミルトン問題として定義する反復アルゴリズムについて述べる。
最短ベクトル問題の数値的な例では、改良された問題列を持つアルゴリズムが所望の解に収束することを示す。
論文 参考訳（メタデータ） (2022-04-28T12:04:03Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳（メタデータ） (2021-05-14T11:31:14Z) - 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) - Quantum Approximation for Wireless Scheduling [11.79760591464748]
本稿では,無線スケジューリング問題に対する量子近似最適化アルゴリズム(QAOA)を提案する。
QAOAは多くのアプリケーションで有望なハイブリッド量子古典アルゴリズムの1つである。
QAOAにインスパイアされたスケジューリングのための量子近似最適化(QAOS)を提案する。
論文 参考訳（メタデータ） (2020-04-14T13:29:22Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。