論文の概要: Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing

• arxiv url: http://arxiv.org/abs/2412.15665v1
• Date: Fri, 20 Dec 2024 08:27:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-23 16:22:51.329460
• Title: Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing
• Title（参考訳）: 自動車配車用分枝価格とカットにおける量子サブルーチン
• Authors: Friedrich Wagner, Frauke Liers,
• Abstract要約: この研究で、限られた資源を持つ量子がNPハード問題に対する大規模な正確な最適化アルゴリズムにどのように統合できるかを実証する。 我々のアルゴリズムの重要な特徴は、量子によって返される最良の解からではなく、あるコスト閾値以下の全ての解から得られることである。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Motivated by recent progress in quantum hardware and algorithms researchers have developed quantum heuristics for optimization problems, aiming for advantages over classical methods. To date, quantum hardware is still error-prone and limited in size such that quantum heuristics cannot be scaled to relevant problem sizes and are often outperformed by their classical counterparts. Moreover, if provably optimal solutions are desired, one has to resort to classical exact methods. As however quantum technologies may improve considerably in future, we demonstrate in this work how quantum heuristics with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. To this end, we consider vehicle routing as prototypical NP-hard problem. We model the pricing and separation subproblems arising in a branch-price-and-cut algorithm as quadratic unconstrained binary optimization problems. This allows to use established quantum heuristics like quantum annealing or the quantum approximate optimization algorithm for their solution. A key feature of our algorithm is that it profits not only from the best solution returned by the quantum heuristic but from all solutions below a certain cost threshold, thereby exploiting the inherent randomness is quantum algorithms. Moreover, we reduce the requirements on quantum hardware since the subproblems, which are solved via quantum heuristics, are smaller than the original problem. We provide an experimental study comparing quantum annealing to simulated annealing and to established classical algorithms in our framework. While our hybrid quantum-classical approach is still outperformed by purely classical methods, our results reveal that both pricing and separation may be well suited for quantum heuristics if quantum hardware improves.
• Abstract（参考訳）: 量子ハードウェアとアルゴリズムの最近の進歩に動機づけられた研究者は、古典的手法よりも優位性を目指して、最適化問題のための量子ヒューリスティックを開発した。 現在まで、量子ハードウェアは依然としてエラーを起こしやすく、量子ヒューリスティックが関連する問題のサイズにスケールできないほどにサイズが制限されており、しばしば古典的なハードウェアよりも優れている。 さらに、証明可能な最適解が望まれるならば、古典的な正確な方法に頼らなければならない。 将来量子技術は大幅に改善される可能性があるが、この研究において、限られた資源を持つ量子ヒューリスティックがNPハード問題に対する大規模な正確な最適化アルゴリズムにどのように統合できるかを実証する。 この目的のために、車両のルーティングをNPハード問題とみなす。 分岐価格とカットアルゴリズムで生じるサブプロブレムの価格と分離を2次非制約バイナリ最適化問題としてモデル化する。 これにより、量子アニールや量子近似最適化アルゴリズムのような確立された量子ヒューリスティックを使用することができる。 我々のアルゴリズムの重要な特徴は、量子ヒューリスティックによって返される最良の解から利益を得るだけでなく、あるコスト閾値以下の全ての解から利益を得るので、固有のランダム性を利用するのは量子アルゴリズムである。 さらに、量子ヒューリスティックによって解かれるサブプロブレムは、元の問題よりも小さいので、量子ハードウェアの要件を小さくする。 我々は、量子アニールとシミュレーションアニールを比較し、我々のフレームワークで確立された古典的アルゴリズムについて実験を行った。 我々のハイブリッド量子-古典的アプローチは、純粋に古典的な手法では依然として優れていますが、量子ハードウェアが改良された場合、価格と分離の両方が量子ヒューリスティックに適していることが明らかになりました。

関連論文リスト

• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。 提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
  論文  参考訳（メタデータ） (2023-04-18T11:57:15Z)
• Quantum-Enhanced Greedy Combinatorial Optimization Solver [12.454028945013924]
  最適化問題を解くために反復量子最適化アルゴリズムを導入する。 72量子ビット以下のプログラム可能な超伝導量子系に量子アルゴリズムを実装した。 量子アルゴリズムは古典的な欲求よりも体系的に優れており、量子エンハンスメントのシグナルとなる。
  論文  参考訳（メタデータ） (2023-03-09T18:59:37Z)
• The Role of Entanglement in Quantum-Relaxation Based Optimization Algorithms [4.00916638804083]
  量子ランダムアクセスコード(QRAC)は、バイナリ最適化の複数の変数を1量子ビットでエンコードする。 この結果から,QRAOは量子コンピュータに制限された二項最適化問題の解決可能なインスタンスをスケールできるだけでなく,量子絡み合いの恩恵を受けることが示唆された。
  論文  参考訳（メタデータ） (2023-02-01T13:24:51Z)
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems [1.1470070927586016]
  量子コンピュータを用いて最適化問題を解く量子最適化の分野について論じる。 適切なユースケースを通じてこれを実証し、量子コンピュータの現在の品質について論じる。 本稿では、最近の量子最適化のブレークスルーと現状と今後の方向性について論じる。
  論文  参考訳（メタデータ） (2022-12-21T12:56:37Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Limitations of variational quantum algorithms: a quantum optimal transport approach [11.202435939275675]
  我々は、ノイズとノイズレスの両体制において、標準NISQ提案の極めて厳密な境界を得る。 境界は、QAOAのような両方の回路モデルアルゴリズムと、量子アニールのような連続時間アルゴリズムの性能を制限する。
  論文  参考訳（メタデータ） (2022-04-07T13:58:44Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• Limitations of optimization algorithms on noisy quantum devices [0.0]
  我々は、古典的アルゴリズムと、短期的な量子デバイス上で動作している量子アルゴリズムを比較する透過的な方法を提案する。 我々のアプローチは、量子状態がノイズモデルの定点にどれだけ早く収束するかを決定するエントロピック不等式の組み合わせに基づいている。
  論文  参考訳（メタデータ） (2020-09-11T17:07:26Z)

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

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