論文の概要: Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem
- arxiv url: http://arxiv.org/abs/2412.07460v1
- Date: Tue, 10 Dec 2024 12:28:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-11 22:09:45.360802
- Title: Accuracy and Performance Evaluation of Quantum, Classical and Hybrid Solvers for the Max-Cut Problem
- Title（参考訳）: Max-Cut問題に対する量子・古典・ハイブリッド解の精度と性能評価
- Authors: Jaka Vodeb, Vid Eržen, Timotej Hrga, Janez Povh,
- Abstract要約: 本稿では,NP-hard Max-Cut 問題と QUBO 問題に対する量子,古典,ハイブリッドの解法の性能について検討する。
我々は,新しい高速アニーリングD-Wave量子処理ユニット(QPU)とD-Wave Hybrid solverを,最先端の古典的アニーリングアルゴリズム(SA)と東芝のシミュレート分岐機(SBM)と比較した。
その結果,グローバルな最適解法が知られている小さなケースでは,ハイブリッドソルバとSAアルゴリズムが一貫してグローバルな最適解法を実現し,QPUを上回っていることがわかった。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper investigates the performance of quantum, classical, and hybrid solvers on the NP-hard Max-Cut and QUBO problems, examining their solution quality relative to the global optima and their computational efficiency. We benchmark the new fast annealing D-Wave quantum processing unit (QPU) and D-Wave Hybrid solver against the state-of-the-art classical simulated annealing algorithm (SA) and Toshiba's simulated bifurcation machine (SBM). Our study leverages three datasets encompassing 139 instances of the Max-Cut problem with sizes ranging from 100 to 10,000 nodes. For instances below 251 nodes, global optima are known and reported, while for larger instances, we utilize the best-known solutions from the literature. Our findings reveal that for the smaller instances where the global optimum is known, the Hybrid solver and SA algorithm consistently achieve the global optimum, outperforming the QPU. For larger instances where global optima are unknown, we observe that the SBM and the slower variant of SA deliver competitive solution quality, while the Hybrid solver and the faster variant of SA performed noticeably worse. Although computing time varies due to differing underlying hardware, the Hybrid solver and the SBM demonstrate both efficient computation times, while for SA reduction in computation time can be achieved at the expense of solution quality.
- Abstract（参考訳）: 本稿では,NP-hard Max-Cut 問題と QUBO 問題に対する量子,古典,ハイブリッドの解法の性能について検討し,その解の最適性とその計算効率について検討する。
我々は,新しい高速アニーリングD-Wave量子処理ユニット (QPU) とD-Wave Hybrid solver を,最先端の古典的アニーリングアルゴリズム (SA) と東芝のシミュレート分岐器 (SBM) と比較した。
本研究は,100ノードから10,000ノード規模のMax-Cut問題の129インスタンスを含む3つのデータセットを活用する。
251ノード以下のインスタンスでは、グローバルオプティマが知られ、報告され、大きなインスタンスでは、文献から最もよく知られたソリューションが利用される。
その結果,グローバルな最適解法が知られている小さなケースでは,ハイブリッドソルバとSAアルゴリズムが一貫してグローバルな最適解法を実現し,QPUを上回っていることがわかった。
グローバル最適値が不明な大規模の場合, SBM と SBM の低変量により, 競合解の質が向上する一方, ハイブリッド・ソルバとより高速な SA は著しく低下した。
計算時間はハードウェアの違いにより異なるが、Hybrid SolutionrとSBMはどちらも効率的な計算時間を示し、SAの削減はソリューションの品質を犠牲にして達成できる。
関連論文リスト
- Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。
本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
論文 参考訳（メタデータ） (2025-04-21T18:19:19Z) - Quantum Annealing for Combinatorial Optimization: A Benchmarking Study [39.125366249242646]
現状の量子解法は,従来の解法よりも精度が0.013%高く,解法時間も6,561xであることを示す。
この結果から,特にハイブリッド構成において,従来のQAよりもQAを活用できるという利点が浮かび上がっている。
論文 参考訳（メタデータ） (2025-04-08T16:43:24Z) - Hybrid Quantum-HPC Solutions for Max-Cut: Bridging Classical and Quantum Algorithms [0.0]
我々は,ハイブリッドシステムにおける時間的複雑性,スケーラビリティ,通信オーバーヘッドを分析する理論的モデルを構築した。
小型のMax-Cutインスタンス上でのQAOAの性能を評価する。
論文 参考訳（メタデータ） (2024-10-21T04:10:54Z) - MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
量子近似最適化アルゴリズム(QAOA)とその変種は、最適化問題に対処する大きな可能性を示している。
良好な性能を実現するために必要な回路深度は問題固有であり、しばしば現在の量子デバイスの最大容量を超える。
ミキサジェネレータネットワーク (MG-Net) は, 最適ミキサハミルトニアンを動的に定式化するための統合ディープラーニングフレームワークである。
論文 参考訳（メタデータ） (2024-09-27T12:28:18Z) - Quantum Computing for MIMO Beam Selection Problem: Model and Optical
Experimental Solution [4.990043560632826]
本研究は, 実用的な5G演算への大きな期待を示し, 通信における計算困難問題の解法における量子コンピューティングの適用を促進する。
大規模マルチインプット・マルチアウトプット(MIMO)は、データレートの向上、信号品質の向上、課題のある環境でのカバレッジ向上などにより、近年広く普及している。
論文 参考訳（メタデータ） (2023-10-19T00:12:20Z) - Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem [8.738180371389097]
量子近似最適化アルゴリズム(QAOA)は、量子コンピュータにおける最適化問題を解くための主要な候補アルゴリズムである。
本稿では,低自己相関二項列(LABS)問題に対するQAOAの広範な数値的な検討を行う。
パラメータが固定されたQAOAのランタイムは、分岐とバウンドの解法よりも良くスケールする。
論文 参考訳（メタデータ） (2023-08-04T14:17:21Z) - Fast Bayesian Optimization of Needle-in-a-Haystack Problems using
Zooming Memory-Based Initialization [73.96101108943986]
Needle-in-a-Haystack問題は、データセットのサイズに対して最適な条件が極端に不均衡であるときに発生する。
本稿では,従来のベイズ最適化原理に基づくズームメモリに基づく初期化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T23:57:41Z) - 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) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。