論文の概要: Solving Large-Scale Vehicle Routing Problems with Hybrid Quantum-Classical Decomposition

• arxiv url: http://arxiv.org/abs/2507.05373v1
• Date: Mon, 07 Jul 2025 18:02:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-09 16:34:37.286999
• Title: Solving Large-Scale Vehicle Routing Problems with Hybrid Quantum-Classical Decomposition
• Title（参考訳）: ハイブリッド量子古典分解による大規模車両ルーティング問題の解法
• Authors: Andrew Maciejunes, John Stenger, Dan Gunlycke, Nikos Chrisochoides,
• Abstract要約: 車両ルーティング問題(VRP)を解決するための2段階分解戦略を提案する。 問題レベル分解は13ノード(156キュービット)のVRPを小さなトラベリングセールスマン問題(TSP)インスタンスに分割する。 提案手法は,回路深さの最大95%の低減,キュービット数の96%の削減,および2キュービットゲート数の99.5%の削減を実現している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a two-level decomposition strategy for solving the Vehicle Routing Problem (VRP) using the Quantum Approximate Optimization Algorithm. A Problem-Level Decomposition partitions a 13-node (156-qubit) VRP into smaller Traveling Salesman Problem (TSP) instances. Each TSP is then further cut via Circuit-Level Decomposition, enabling execution on near-term quantum devices. Our approach achieves up to 95\% reductions in the circuit depth, 96\% reduction in the number of qubits and a 99.5\% reduction in the number of 2-qubit gates. We demonstrate this hybrid algorithm on the standard edge encoding of the VRP as well as a novel amplitude encoding. These results demonstrate the feasibility of solving VRPs previously too complex for quantum simulators and provide early evidence of potential quantum utility.
• Abstract（参考訳）: 本稿では、量子近似最適化アルゴリズムを用いて、車両ルーティング問題(VRP)を解決するための2段階分解戦略を提案する。 問題レベル分解は13ノード(156キュービット)のVRPを小さなトラベリングセールスマン問題(TSP)インスタンスに分割する。 各TSPはCircuit-Level Decompositionによってさらにカットされ、短期量子デバイス上での実行が可能である。 提案手法は,回路深さの最大95.%,キュービット数の96.%,2キュービットゲート数の99.5.%の削減を実現する。 本稿では,VRPの標準エッジエンコーディングと新しい振幅エンコーディングを併用したハイブリッドアルゴリズムについて述べる。 これらの結果は、以前は量子シミュレーターには複雑すぎるVRPを解く可能性を示し、潜在的な量子ユーティリティーの早期の証拠を提供する。

関連論文リスト

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  本稿では,2つの分解法,すなわちグラフ縮小と回路切断の精巧な組み合わせを提案する。 この結果から,現在の量子技術の制約内での最適化問題に対するアルゴリズムの性能に関する知見が得られた。
  論文  参考訳（メタデータ） (2024-04-08T14:19:25Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
  論文  参考訳（メタデータ） (2023-06-14T13:44:35Z)
• Efficient MILP Decomposition in Quantum Computing for ReLU Network Robustness [2.854196251981274]
  本研究では,MILP(Mixed-Integer Linear Programming)の2つの分解法について検討した。 我々は、元の問題をより小さなサブプロブレムに分割することに集中し、量子古典的ハードウェアのアプローチを組み合わせて反復的に解決する。 実験の結果,従来の量子アニール法やゲートベース量子コンピュータと比較して最大90%の量子ビットを削減できることがわかった。
  論文  参考訳（メタデータ） (2023-04-30T13:10:56Z)
• Reducing the Depth of Linear Reversible Quantum Circuits [0.0]
  量子コンピューティングでは、量子ビットのデコヒーレンス時間が計算時間を決定する。 本稿では,既存のアルゴリズムの2倍の浅さの量子回路を生成する分割・征服アルゴリズムの実用的な定式化を提案する。 全体としては、可逆関数のクラス全体の深さを一貫して減らし、アンシラフリーケースでは最大92%、アシラリーキュービットが利用可能であれば最大99%に抑えることができる。
  論文  参考訳（メタデータ） (2022-01-17T12:36:32Z)
• Optimized fermionic SWAP networks with equivalent circuit averaging for QAOA [2.3362993651992863]
  量子近似最適化アルゴリズム(QAOA)のためのフェミオンSWAPネットワークの実行を最適化する。 等価回路平均化(Equivalent Circuit Averaging)を導入し,量子回路コンパイルにおける自由度をランダム化する。 超伝導量子プロセッサ上の4つのトランスモン量子ビット上での深さp = 1のQAOAの誤差(経時変化距離)を平均60%低減する。
  論文  参考訳（メタデータ） (2021-11-08T15:32:05Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz [68.8204255655161]
  本稿では,変分量子固有解法(VQE)アルゴリズムのコンパイル戦略について述べる。 我々は、回路深さとゲート数を減らすために、ユニタリ結合クラスタ(UCC)アンサッツを使用する。
  論文  参考訳（メタデータ） (2020-07-20T22:26:16Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)

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

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