論文の概要: Stochastic Simulated Quantum Annealing for Fast Solution of
Combinatorial Optimization Problems
- arxiv url: http://arxiv.org/abs/2302.12454v3
- Date: Thu, 29 Jun 2023 03:23:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-30 19:16:37.391758
- Title: Stochastic Simulated Quantum Annealing for Fast Solution of
Combinatorial Optimization Problems
- Title（参考訳）: 組合せ最適化問題の高速解に対する確率的量子アニーリング
- Authors: Naoya Onizawa and Ryoma Sasaki and Duckgyu Shin and Warren J. Gross
and Takahiro Hanyu
- Abstract要約: SSQAは計算と量子モンテカルロに基づいて設計されている。
QAと比較して100倍の問題を処理でき、従来のSA法よりも大きい問題を処理できる。
- 参考スコア（独自算出の注目度）: 9.516147599772243
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we introduce stochastic simulated quantum annealing (SSQA) for
large-scale combinatorial optimization problems. SSQA is designed based on
stochastic computing and quantum Monte Carlo, which can simulate quantum
annealing (QA) by using multiple replicas of spins (probabilistic bits) in
classical computing. The use of stochastic computing leads to an efficient
parallel spin-state update algorithm, enabling quick search for a solution
around the global minimum energy. Therefore, SSQA realizes quantum-like
annealing for large-scale problems and can handle fully connected models in
combinatorial optimization, unlike QA. The proposed method is evaluated in
MATLAB on graph isomorphism problems, which are typical combinatorial
optimization problems. The proposed method achieves a convergence speed an
order of magnitude faster than a conventional stochastic simulaated annealing
method. Additionally, it can handle a 100-times larger problem size compared to
QA and a 25-times larger problem size compared to a traditional SA method,
respectively, for similar convergence probabilities.
- Abstract（参考訳）: 本稿では,大規模組合せ最適化問題に対する確率的量子アニール法(SSQA)を提案する。
SSQAは確率計算と量子モンテカルロに基づいて設計されており、古典計算において複数のスピン(確率ビット)のレプリカを使用することで量子アニール(QA)をシミュレートすることができる。
確率計算を用いることで、効率的な並列スピン状態更新アルゴリズムが実現し、世界最小エネルギーに関する解を素早く探索することができる。
したがって、SSQAは大規模な問題に対して量子的アニールを実現し、QAとは異なり、完全に連結されたモデルを組合せ最適化で扱うことができる。
提案手法は,典型的な組合せ最適化問題であるグラフ同型問題に対してMATLABで評価する。
提案手法は,従来の確率的擬似焼鈍法よりもはるかに高速な収束速度を実現する。
さらに、従来のSA法と比較して、QAよりも100倍大きい問題サイズと25倍大きい問題サイズを同様の収束確率で処理することができる。
関連論文リスト
- 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) - Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
既存の量子最適化手法のいくつかは、最適量子状態から最も高い確率で測定される二項解を求める解法に統一可能であることを示す。
テンソルネットワーク技術を用いたMAX-CUT問題における数百ノードの標準ベンチマークグラフの実験は、RQRAOがゴーマン-ウィリアムソン法より優れ、最先端の古典的解法に匹敵することを示した。
論文 参考訳（メタデータ） (2024-03-04T13:48:21Z) - Quantum Approximate Optimisation for Not-All-Equal SAT [9.427635404752936]
変動量子アルゴリズムのQAOAを、満足度問題(SAT: Not-All-Equal SAT)の変種に適用する。
両ソルバのランタイムは問題サイズとともに指数関数的にスケールするが,QAOAのスケーリングは回路深さが十分に大きい場合に小さくなることを示す。
論文 参考訳（メタデータ） (2024-01-05T15:11:24Z) - 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) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳（メタデータ） (2021-11-30T12:21:41Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Warm-starting quantum optimization [6.832341432995627]
最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。
これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。
同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
論文 参考訳（メタデータ） (2020-09-21T18:00:09Z) - An adaptive quantum approximate optimization algorithm for solving
combinatorial problems on a quantum computer [0.0]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くハイブリッド変分量子古典アルゴリズムである。
我々は,QAOAの反復バージョンを開発し,特定のハードウェア制約に適応することができる。
アルゴリズムをMax-Cutグラフのクラス上でシミュレートし、標準QAOAよりもはるかに高速に収束することを示す。
論文 参考訳（メタデータ） (2020-05-20T18:00:01Z) - Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical
and Quantum Computers [3.04585143845864]
本稿では,2次最適化問題に対する現行手法の適用性を高めるために,分解に基づくアプローチを提案する。
我々は、乗算器の交互方向法(ADMM)が、MBOを二項制約のない問題(量子アルゴリズムで解ける)に分割できることを示した。
提案手法の有効性は,Qiskit で実装された量子回路上での VQE と QAOA を用いたシミュレーションにより,いくつかの最適化問題に対して得られた数値結果によって示される。
論文 参考訳（メタデータ） (2020-01-07T14:43:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。