論文の概要: Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2602.06171v1
• Date: Thu, 05 Feb 2026 20:20:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.097181
• Title: Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization
• Title（参考訳）: 組合せ最適化のための量子強化マルコフ連鎖モンテカルロ
• Authors: Kate V. Marshall, Daniel J. Egger, Michael Garn, Francesca Schiavello, Sebastian Brandhofer, Christa Zoufal, Stefan Woerner,
• Abstract要約: 本研究では,短期量子コンピューティングによる古典的最適化にアプローチする別の方法を提案する。 我々は,IBM量子ハードウェア上の117量子ビットを用いて,最大セット問題(MIS)のインスタンスのグローバル最適化を最大117個の決定変数に復元することを示した。
• 参考スコア（独自算出の注目度）: 1.009951593136676
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.
• Abstract（参考訳）: 量子コンピューティングは、古典計算と比較して組合せ最適化問題に対処するための代替パラダイムを提供する。 最近のハードウェアの改善にもかかわらず、最先端の古典的解法では難しいことが知られているスケールでの経験的量子最適化実験の実行はまだ到達していない。 本研究では、短期量子コンピューティングによる組合せ最適化にアプローチする別の方法を提案する。 複雑な確率分布を近似するために量子化マルコフ連鎖モンテカルロ(QeMCMC)を用いて観測された有望な結果に触発された我々は、組み合わせ最適化の文脈において、デバイスからのサンプリングとQeMCMCとウォームスタートと並列テンパリングのアイデアを組み合わせる。 我々は,IBM量子ハードウェア上での117量子ビットを用いて,最大独立セット問題(MIS)のインスタンスのグローバル最適化を最大117個の決定変数まで回復することを示す。 選択したMISの場合と同様の古典的手法と比較して,我々のアルゴリズムのスケーリング優位性を示す初期の証拠を示す。 MISは、金融サービスや分子生物学といった分野において実質的に関係があり、場合によっては、数百の決定変数だけで古典的に最適に解決することがすでに困難である。

関連論文リスト

• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  本稿では,NP-hard問題に対する量子最適化手法の評価を目的とした,包括的なベンチマークフレームワークを提案する。 本フレームワークは,多次元クナップサック問題(MDKP),最大独立集合(MIS),二次割当問題(QAP),市場シェア問題(MSP)など,主要な課題に重点を置いている。
  論文  参考訳（メタデータ） (2025-03-15T13:02:22Z)
• Performant near-term quantum combinatorial optimization [1.1999555634662633]
  線形深度回路を用いた最適化問題に対する変分量子アルゴリズムを提案する。 我々のアルゴリズムは、ターゲット量子関数の各項を制御するために設計されたハミルトン生成器からなるアンサッツを使用する。 性能と資源最小化のアプローチは、潜在的な量子計算上の利点の候補として有望である、と結論付けます。
  論文  参考訳（メタデータ） (2024-04-24T18:49:07Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。 この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。 我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
  論文  参考訳（メタデータ） (2023-06-15T15:28:12Z)
• Classically-Boosted Quantum Optimization Algorithm [0.0]
  我々は、量子最適化を強化するために既存の古典的手法を活用する自然なアプローチを探求する。 具体的には、近似解を見つけるために古典的なアルゴリズムを実行し、量子回路を用いて高品質な解の「近傍」を探索する。 CBQOA の Max 3SAT および Max Bisection への応用を実証し,これらの問題に対する従来のアプローチよりも優れていることを示す実証的証拠を提供する。
  論文  参考訳（メタデータ） (2022-03-25T23:36:14Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Markov Chain Monte-Carlo Enhanced Variational Quantum Algorithms [0.0]
  本稿では,モンテカルロ法を用いて解析的境界を時間複雑度に設定する変動量子アルゴリズムを提案する。 提案手法の有効性と,MaxCutインスタンスの量子回路シミュレーションによる解析の有効性を実証する。
  論文  参考訳（メタデータ） (2021-12-03T23:03:44Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。 プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
  論文  参考訳（メタデータ） (2021-11-30T12:21:41Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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