論文の概要: Comparing classical and quantum QUBO solvers: optimality, trajectory diagnostics, and limits of solver selection

• arxiv url: http://arxiv.org/abs/2610.35126v1
• Date: Mon, 26 Oct 2026 10:01:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-29 18:27:44.875392
• Title: Comparing classical and quantum QUBO solvers: optimality, trajectory diagnostics, and limits of solver selection
• Title（参考訳）: 古典的および量子的QUBO解法の比較:最適性、軌道診断、解法選択の限界
• Abstract要約: 古典的, テンソルネットワーク, 固定スケジュール量子アプローチを, 14-48変数を持つ10の族から180のベンチマークインスタンスで比較した。 メインベンチマークでは、汎用ブランチ・アンド・カット・ソルバが600,sの上限内で176のインスタンスを認証する。 パラレル・テンパリングは 60の予算で全ての テスト走行で最適に到達します
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Comparing solvers for quadratic unconstrained binary optimization (QUBO) requires distinguishing solution quality from optimality certification. We compare classical, tensor-network, and fixed-schedule quantum approaches on 180 benchmark instances from ten families with 14-48 variables, supplemented by harder synthetic instances with known optimal solutions, extending to 128 variables. On the main benchmark, a general-purpose branch-and-cut solver matches all reference energies and certifies 176 instances within a 600,s cap. When the known optima are moved to randomly chosen bitstrings, the search comparison changes: at n = 48 the branch-and-cut solver finds only four of ten optima and certifies none, whereas parallel tempering reaches every optimum in every tested run at a 60,s budget. Structural and trajectory diagnostics explain aspects of tensor-network performance. A treewidth bound ranks trajectory bond-dimension demand at Spearman $ρ= 0.78$ in sample and $0.73$ out of sample, but provides only a coarse runtime estimate. Controlled experiments identify excited-state trapping during warm-started density-matrix renormalization group (DMRG) sweeps and demonstrate mitigation by restarting the variational search. These diagnostics do not yield a validated solver-selection rule. The tested linear-ramp quantum approximate optimization algorithm (LR-QAOA) runs offer no solution-quality improvement over the classical comparators. In the separate Wishart scaling study, on the harder setting, none of the classical methods tested reaches the optimum at the sampled sizes from n = 72 onward within the tested budgets. While this does not provide evidence for quantum advantage, it identifies a domain for further investigation.
• Abstract（参考訳）: 2次非制約バイナリ最適化(QUBO)の解法の比較では、最適性証明と解の質を区別する必要がある。 古典的, テンソルネットワーク, 固定スケジュール量子アプローチを, 14-48変数を持つ10種類のベンチマークインスタンスで比較し, 既知の最適解を持つより複雑な合成インスタンスで補足し, 128変数まで拡張した。 メインベンチマークでは、汎用ブランチ・アンド・カット・ソルバがすべての参照エネルギーと一致し、600,sの上限内で176のインスタンスを認証する。 既知のオプティマがランダムに選択されたビットストリングに移動すると、探索比較は変化する: n = 48 では、ブランチ・アンド・カットのソルバは10のオプティマのうち4つしか見つからず、何も証明しない。 構造的および軌道的診断はテンソルネットワーク性能の側面を説明する。 木幅境界は、Spearman $ρ= 0.78$、サンプルから0.73$の軌道的結合次元需要をランク付けするが、粗い実行時推定のみを提供する。 制御された実験では、温度開始した密度行列再正規化群(DMRG)における励起状態のトラップを同定し、変分探索を再開することで緩和効果を示す。 これらの診断は、検証された解法選択則を導出しない。 テストされた線形ランプ量子近似最適化アルゴリズム(LR-QAOA)は、古典的なコンパレータよりも解品質が向上しない。 ウィッシュアートの別のスケールスタディでは、より難しい設定では、テストされた古典的手法は、試験された予算の中でn = 72 から標本化されたサイズで最適に達することはない。 これは量子上の優位性を示す証拠を示さないが、さらなる研究のための領域を特定できる。

関連論文リスト

• Quantum Variational Approaches to the Maximum Independent Set Problem at Utility Scale [6.404616027487662]
  最大独立集合(MIS)問題に対する変分量子アルゴリズムを64,99,180頂点のベンチマークグラフ上で検討する。 新しい構成により、複数のシードを同時に量子並列変動探索することができ、単一シードのメソッドが失敗する正確なMISを発見することができる。 IBM Quantumハードウェア ibm_marrakesh のハードウェア検証では、収束したシミュレータパラメータがノイズの多い量子実行に効果的に転送されることを確認した。
  論文  参考訳（メタデータ） (2026-06-27T11:15:45Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Quantum King-Ring Domination in Chess: A QAOA Approach [2.7474031534471384]
  量子キングリング・ドミネーション(Quantum King-Ring Domination、QKRD)は、チェスの戦術的位置から派生したNISQスケールのベンチマークである。 我々はQAOA設計選択を体系的に評価し、制約保存ミキサーが標準ミキサーよりも約13ステップ早く収束していることを見出した。 内在的検証では、QAOAはグリーディを12.6%、ランダム選択を80.1%上回っている。
  論文  参考訳（メタデータ） (2026-01-01T11:59:40Z)
• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  既存の量子処理ユニット(QPU)がマルチレベル戦略においてサブソルバとしてどのように機能するかを実験的に検証する。 完全連結な 82$-qubit Sherrington-Kirkpatrick グラフに対して 10$ の近似解を求める。 量子最適化の結果は古典学と比較して解の質に関して競争力がある。
  論文  参考訳（メタデータ） (2024-08-14T20:06:32Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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