論文の概要: Stochastic Quantum Monte Carlo Algorithm for Large-Scale Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2302.12454v1
• Date: Fri, 24 Feb 2023 05:08:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-27 14:33:03.462551
• Title: Stochastic Quantum Monte Carlo Algorithm for Large-Scale Combinatorial Optimization Problems
• Title（参考訳）: 大規模組合せ最適化問題に対する確率量子モンテカルロアルゴリズム
• Authors: Naoya Onizawa and Ryoma Sasaki and Duckgyu Shin and Warren J. Gross and Takahiro Hanyu
• Abstract要約: 大規模最適化問題に対する量子モンテカルロ (QMC) アルゴリズムを提案する。 QMCは、スピンの複数のレプリカを使用して量子アニール(QA)を模倣することができる。 D-Wave Two QA マシンよりも 2 桁大きな問題を解く。
• 参考スコア（独自算出の注目度）: 9.516147599772243
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this brief, we introduce a quantum Monte Carlo (QMC) algorithm based on stochastic computing for large-scale combinatorial optimization problems. QMC can mimic quantum annealing (QA) using multiple replicas of spins (probabilistic bits) based on the Trotter-Suzuki decomposition in classical computing. Hence, it realizes both quantum-like annealing for large-scale problems and handles fully connected models in combinatorial optimization, unlike QA. Stochastic computing realizes an efficient spin-state update algorithm for QMC, which can quickly search for a solution around the global minimum energy. The proposed annealing method is evaluated in MATLAB on graph isomorphism problems as a typical combinatorial optimization problem. The proposed method achieves a convergence speed an order of magnitude faster than that of a simulated annealing method based on stochastic computing. In addition, it solves problems using two orders-of-magnitude larger number of spins than the D-Wave Two QA machine.
• Abstract（参考訳）: 本稿では,大規模組合せ最適化問題に対する確率計算に基づく量子モンテカルロ(qmc)アルゴリズムを提案する。 QMCは古典計算におけるトロッタースズキ分解に基づくスピンの複数のレプリカ(確率ビット)を用いて量子アニール(QA)を模倣することができる。 したがって、大規模問題に対する量子的なアニーリングの両方を実現し、qaとは異なり、組合せ最適化において完全連結モデルを扱う。 確率計算はQMCの効率的なスピン状態更新アルゴリズムを実現する。 提案手法はグラフ同型問題に対してMATLABにおいて典型的な組合せ最適化問題として評価される。 提案手法は,確率計算に基づく模擬アニール法よりもはるかに高速な収束速度を実現する。 さらに、D-Wave Two QAマシンよりも2桁のスピン数で問題を解く。

関連論文リスト

• 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)

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

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