論文の概要: A comprehensive benchmark of an Ising machine on the Max-Cut problem

• arxiv url: http://arxiv.org/abs/2507.22117v1
• Date: Tue, 29 Jul 2025 18:00:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-31 16:14:17.784473
• Title: A comprehensive benchmark of an Ising machine on the Max-Cut problem
• Title（参考訳）: Max-Cut問題におけるIsingマシンの総合ベンチマーク
• Authors: Salwa Shaglel, Markus Kirsch, Marten Winkler, Christian Münch, Stefan Walter, Fritz Schinkel, Martin Kliesch,
• Abstract要約: 富士通のDigital Annealer(DA)をMax-Cut問題でベンチマークする。 最大53,000変数のグラフ上で他のアルゴリズムをリードする上で、包括的なベンチマークを行う。 DAが競争結果をもたらすことが分かっています。
• 参考スコア（独自算出の注目度）: 0.15705429611931052
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: QUBO formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu's Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum-classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2,000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.
• Abstract（参考訳）: 組合せ最適化問題のQUBO定式化は、様々な量子ヒューリスティックを用いてそれらを解くことができる。 大規模な量子計算はまだ手に入らないが、このQUBOの定式化はおそらく驚くほど大きな規模で、すでに数値的にテストできる。 本研究では,富士通のDigital Annealer(DA)をMax-Cut問題にベンチマークし,QUBO問題の主な複雑性を捉える。 ウォールクロック時間に着目し,最大53,000変数のグラフ上の他のヒューリスティックアルゴリズムに対する包括的なベンチマークを行う。 さらに、D-Waveハイブリッド量子古典アニールと最近提案されたQIS3ヒューリスティックの性能結果と比較した。 MQLibの2000以上のグラフのパフォーマンス統計から、DAが競合する結果をもたらすことが分かる。 このベンチマークは、現在、大規模なQUBOインスタンスがヒューリスティックに解決できる範囲を示し、異なる解決者間で一貫した結果をもたらすことを願っている。

関連論文リスト

• A Novel Solver for QUBO Problems: Performance Analysis and Comparative Study with State-of-the-Art Algorithms [18.408755407920744]
  本稿では,分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分枝分数分法,および分枝分枝分枝分枝分根分枝分枝分枝分枝分 我々は、遺伝的アルゴリズム、コヒーレントなイジングマシン、シミュレートされた分岐を含む8つの最先端の解法に対して、QIS3をベンチマークする。 均一なランタイム予算の下で、QIS3は、ほぼすべてのインスタンスで最高のソリューションを獲得し、最大カットインスタンスの94%で最適性を達成する。
  論文  参考訳（メタデータ） (2025-06-05T03:22:48Z)
• Benchmarking Quantum Heuristics: Non-Variational QWOA for Weighted Maxcut [3.3446678075435523]
  非変分量子ウォーク最適化アルゴリズム(非変分QWOA)のベンチマーク結果を示す。 このアルゴリズムは, 問題サイズを最大31$まで超えた大域的最適解に対して, 一定の平均ケース測定確率を達成する。 同じベンチマークインスタンス上での2つのローカル検索のパフォーマンス比較は、非変分QWOAが問題サイズをより適切にスケーリングすることで有意義な優位性をもたらすことを示唆している。
  論文  参考訳（メタデータ） (2025-05-30T04:02:46Z)
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking [1.6385815610837167]
  我々は,多数の小さな離散係数スピングラスイジングモデルを融合させることにより,ポジフォーム植込みQUBOを計算的に困難にすることを検討する。 3つのD-Wave超伝導量子アニーリングプロセッサの性能をベンチマークする。 D-Wave QPUの地中サンプリング成功率は、我々が採用するランダムQUBOのサイズに対して変化しないことがわかった。
  論文  参考訳（メタデータ） (2024-11-06T02:46:33Z)
• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。 本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。 本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
  論文  参考訳（メタデータ） (2024-07-29T17:13:01Z)
• Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
  AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。 本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。 最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。 これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
  論文  参考訳（メタデータ） (2023-10-18T17:59:45Z)
• Shuffle-QUDIO: accelerate distributed VQE with trainability enhancement and measurement reduction [77.97248520278123]
  本稿では,量子分散最適化におけるシャッフル演算を局所ハミルトニアンに組み込むためのShuffle-QUDIOを提案する。 QUDIOと比較して、Shuffle-QUDIOは量子プロセッサ間の通信周波数を著しく低減し、同時にトレーニング性を向上させる。
  論文  参考訳（メタデータ） (2022-09-26T06:51:20Z)
• 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)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Finding Small and Large k-Clique Instances on a Quantum Computer [1.1602089225841632]
  三角フィニング問題とそのNP-ハードk-斜め一般化に対するゲートベースアプローチを提案する。 本研究では,雑音型中間規模量子コンピュータ(NISQ)デバイス上での短期的実装のための定数要因と,量子コンピュータの長期使用評価における問題のスケーリングについて検討する。
  論文  参考訳（メタデータ） (2020-08-28T07:40:44Z)

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

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