論文の概要: Solving QUBOs with a quantum-amenable branch and bound method
- arxiv url: http://arxiv.org/abs/2407.20185v1
- Date: Mon, 29 Jul 2024 17:13:01 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-30 12:45:22.740763
- Title: Solving QUBOs with a quantum-amenable branch and bound method
- Title（参考訳）: 量子可換分岐と有界法によるQUBOの解法
- Authors: Thomas Häner, Kyle E. C. Booth, Sima E. Borujeni, Elton Yechao Zhu,
- Abstract要約: 本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。
本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。
本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
- 参考スコア（独自算出の注目度）: 0.3749861135832072
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Due to the expected disparity in quantum vs. classical clock speeds, quantum advantage for branch and bound algorithms is more likely achievable in settings involving large search trees and low operator evaluation costs. Therefore, in this paper, we describe and experimentally validate an exact classical branch and bound solver for quadratic unconstrained binary optimization (QUBO) problems that matches these criteria. Our solver leverages cheap-to-implement bounds from the literature previously proposed for Ising models, including that of Hartwig, Daske, and Kobe from 1984. We detail a variety of techniques from high-performance computing and operations research used to boost solver performance, including a global variable reordering heuristic, a primal heuristic based on simulated annealing, and a truncated computation of the recursive bound. We also outline a number of simple and inexpensive bound extrapolation techniques. Finally, we conduct an extensive empirical analysis of our solver, comparing its performance to state-of-the-art QUBO and MaxCut solvers, and discuss the challenges of a speedup via quantum branch and bound beyond those faced by any quadratic quantum speedup.
- Abstract（参考訳）: 量子と古典的なクロック速度の相違により、大きな探索木と低い演算子評価コストを含む設定において、分岐と有界アルゴリズムの量子的優位性はより達成可能である。
そこで本稿では,これらの基準に適合する2次非制約二元最適化(QUBO)問題に対して,古典的分岐と有界解法を記述し,実験的に検証する。
本稿では,1984年に提案したIsingモデルから,Hartwig,Daske,Koberなど,安価な実装バウンダリを利用する。
本稿では,大域的変数並べ替えヒューリスティック,シミュレートされたアニーリングに基づく原始ヒューリスティック,再帰的境界の切り離された計算など,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について述べる。
また、単純で安価な境界外挿法についても概説する。
最後に、その性能を最先端のQUBOやMaxCutの解法と比較し、量子分岐によるスピードアップの課題を議論し、二次的な量子スピードアップに直面するものを超えている。
関連論文リスト
- Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。
我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。
以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
論文 参考訳（メタデータ） (2024-10-30T08:41:29Z) - 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) - Fast Numerical Solver of Ising Optimization Problems via Pruning and Domain Selection [4.460518115427853]
本稿では,Ising最適化問題に対する高速かつ効率的な解法を提案する。
我々の解法は古典的解法よりも桁違いに高速で、量子インスパイアされたアニールよりも少なくとも2倍高速である。
論文 参考訳（メタデータ） (2023-12-10T09:43:15Z) - Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。
O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。
線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文 参考訳（メタデータ） (2023-10-09T03:10:42Z) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
本研究では,最適化のための量子および古典的手法の可能性を統合する。
線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。
実量子ハードウェアの計算結果を多数提示する。
論文 参考訳（メタデータ） (2023-02-10T20:12:53Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
Bin Packing Problem (BPP) は、ロジスティクスにおけるパラダイム最適化問題として際立っている。
我々は最近,一次元BPPに対するハイブリッドアプローチを提案している。
他の古典的手法と比較する。
論文 参考訳（メタデータ） (2022-07-15T13:09:12Z) - 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) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - An investigation of IBM Quantum Computing device performance on
Combinatorial Optimisation Problems [0.0]
本稿では,古典的および量子的最適化アルゴリズムの性能を近似して,トラベリングセールスマン問題(TSP)と二次割り当て問題(QAP)の2つの共通COPを解く。
2つの古典的最適化法であるブランチ・アンド・バウンド (BNB) とシミュレート・アニーリング (SA) を、変分量子固有解法 (VQE) と量子近似最適化アルゴリズム (QAOA) の2つの量子最適化法と比較した。
以上の結果から,VQEはこれらの指標に対してQAOAよりも優れた性能を示した。
論文 参考訳（メタデータ） (2021-07-08T07:02:50Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。