論文の概要: Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms

• arxiv url: http://arxiv.org/abs/2210.03210v1
• Date: Thu, 6 Oct 2022 21:08:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-23 14:33:03.824632
• Title: Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms
• Title（参考訳）: 分枝・分枝・分枝・分枝・木探索アルゴリズムのためのユニバーサル量子スピードアップ
• Authors: Shouvanik Chakrabarti, Pierre Minssen, Romina Yalovetzky, Marco Pistoia
• Abstract要約: 混合プログラム(MIP)は、コンピュータサイエンス、オペレーションリサーチ、ファイナンシャルエンジニアリングに関心を持つ多くの最適化問題をモデル化する。 Branch-and-Cutアルゴリズムは、ブランチ・アンド・バウンド論理とカットプレーンルーチンを組み合わせることで、現代のMIPソルバのコアとなる。 本稿では,古典的分岐と境界のアルゴリズムを用いた量子アルゴリズムIncremental-Quantum-Branch-and-Boundを提案する。
• 参考スコア（独自算出の注目度）: 13.152347996965297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed Integer Programs (MIPs) model many optimization problems of interest in Computer Science, Operations Research, and Financial Engineering. Solving MIPs is NP-Hard in general, but several solvers have found success in obtaining near-optimal solutions for problems of intermediate size. Branch-and-Cut algorithms, which combine Branch-and-Bound logic with cutting-plane routines, are at the core of modern MIP solvers. Montanaro proposed a quantum algorithm with a near-quadratic speedup compared to classical Branch-and-Bound algorithms in the worst case, when every optimal solution is desired. In practice, however, a near-optimal solution is satisfactory, and by leveraging tree-search heuristics to search only a portion of the solution tree, classical algorithms can perform much better than the worst-case guarantee. In this paper, we propose a quantum algorithm, Incremental-Quantum-Branch-and-Bound, with universal near-quadratic speedup over classical Branch-and-Bound algorithms for every input, i.e., if classical Branch-and-Bound has complexity $Q$ on an instance that leads to solution depth $d$, Incremental-Quantum-Branch-and-Bound offers the same guarantees with a complexity of $\tilde{O}(\sqrt{Q}d)$. Our results are valid for a wide variety of search heuristics, including depth-based, cost-based, and $A^{\ast}$ heuristics. Universal speedups are also obtained for Branch-and-Cut as well as heuristic tree search. Our algorithms are directly comparable to commercial MIP solvers, and guarantee near quadratic speedup whenever $Q \gg d$. We use numerical simulation to verify that $Q \gg d$ for typical instances of the Sherrington-Kirkpatrick model, Maximum Independent Set, and Portfolio Optimization; as well as to extrapolate the dependence of $Q$ on input size parameters. This allows us to project the typical performance of our quantum algorithms for these important problems.
• Abstract（参考訳）: MIP(Mixed Integer Programs)は、コンピュータサイエンス、オペレーションリサーチ、ファイナンシャルエンジニアリングにおける多くの最適化問題をモデル化する。 MIPを解くことは一般にNP-Hardであるが、中間サイズの問題に対して最適に近い解を得ることに成功した。 分岐・切断アルゴリズムは、分岐・境界論理と切断平面ルーチンを組み合わせたもので、現代のmipソルバの核心にある。 モンタナロは、全ての最適解が要求される最悪の場合において、古典的分岐・境界アルゴリズムと比較して、極小に近い速度アップを持つ量子アルゴリズムを提案した。 しかし、実際には、準最適解は十分であり、木探索ヒューリスティックを利用して解木の一部のみを探索することで、古典的アルゴリズムは最悪の場合の保証よりもはるかに優れた性能を発揮する。 本稿では,各入力に対する古典的分岐・境界アルゴリズムに対する普遍的近似量子速度アップを持つ量子アルゴリズム,インクリメンタル量子分岐・境界アルゴリズム,すなわち,古典的分岐・境界アルゴリズムの複雑性が解深さ$d$となる場合,インクリメンタル量子分岐・境界は$\tilde{o}(\sqrt{q}d)$という計算量で同じ保証を提供する。 我々の結果は、深さベース、コストベース、および$A^{\ast}$ヒューリスティックスを含む、幅広い検索ヒューリスティックに有効である。 分枝木探索や加湿木探索にもユニバーサル・スピードアップが得られた。 我々のアルゴリズムは商用のMIPソルバと直接的に同等であり、$Q \gg d$ のときにほぼ2次スピードアップを保証する。 本稿では,Sherrington-Kirkpatrickモデル,Maximum Independent Set,Portfolio Optimizationの典型的な例に対する$Q \gg d$の数値シミュレーションを行い,入力サイズパラメータに対する$Q$の依存性を推定する。 これにより、これらの重要な問題に対する量子アルゴリズムの典型的な性能を予測できる。

関連論文リスト

• 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)
• 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)
• Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
  確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。 従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。 Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
  論文  参考訳（メタデータ） (2023-04-06T02:18:52Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• 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)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。 このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-14T11:12:32Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
  論文  参考訳（メタデータ） (2021-03-03T22:42:15Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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