論文の概要: Quantum walk-based optimisation for capacitated vehicle routing with homogeneous and heterogeneous fleets

• arxiv url: http://arxiv.org/abs/2606.12856v1
• Date: Thu, 11 Jun 2026 03:39:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-12 15:55:27.564866
• Title: Quantum walk-based optimisation for capacitated vehicle routing with homogeneous and heterogeneous fleets
• Title（参考訳）: 量子ウォークに基づく均質および不均一な車両によるキャパシタント車両ルーティングの最適化
• Authors: Edric Matwiejew, Aidan Smith, Callum Neill, Paulo Santos, Ugo Varetto, Jingbo Wang,
• Abstract要約: 容量化車両ルーティング問題(CVRP)は、その目的的複雑さと実用的重要性から、量子最適化の魅力的な候補である。 我々は、同種または異種車両のCVRPに対する量子ウォークに基づく最適化(QWOA)を導入し、製品空間上の連続的な量子ウォークを通してこの問題に対処する。 従来のQWOAベースの定式化とは対照的に、このアプローチは層ごとのゲートの複雑さを$mathcalO(n3log n)$から$mathcalO(n2log n)$に減らす。
• 参考スコア（独自算出の注目度）: 3.6100252173467537
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The capacitated vehicle routing problem (CVRP) is an appealing candidate for quantum optimisation due to its combinatorial complexity and practical importance. However, the problem's constrained search space poses a challenge for such quantum algorithms. We introduce a quantum walk-based optimisation algorithm (QWOA) for the CVRP with homogeneous or heterogeneous vehicle fleets, addressing this challenge through a continuous-time quantum walk over a product space that coincides with combinatorial structures intrinsic to the CVRP solution space. Relative to the prior QWOA-based formulation, this approach reduces the per-layer gate complexity from $\mathcal{O}(n^{3}\log n)$ to $\mathcal{O}(n^{2}\log n)$ and supports a circuit parameterisation schedule generated by a fixed number of classical parameters. Exact state-vector simulation on instances with up to $n=8$ customers and $K=3$ vehicles demonstrates improved convergence to low-cost solutions using markedly fewer objective function evaluations, with the advantage broadening as problem size increases. These results identify structured product-space walks as a promising tool for optimisation over constrained combinatorial spaces.
• Abstract（参考訳）: 容量化車両ルーティング問題(CVRP)は、その組合せ複雑性と実用上の重要性から、量子最適化の魅力的な候補である。 しかし、問題の制約付き探索空間はそのような量子アルゴリズムに挑戦する。 我々は、CVRPソリューション空間に固有の組合せ構造と一致する製品空間上の連続的な量子ウォークを通じて、同種または異種車両群によるCVRPに対する量子ウォークに基づく最適化アルゴリズム(QWOA)を導入する。 従来のQWOAベースの定式化とは対照的に、このアプローチは層ごとのゲートの複雑さを$\mathcal{O}(n^{3}\log n)$から$\mathcal{O}(n^{2}\log n)$に減らし、固定数の古典的パラメータによって生成される回路パラメータ化スケジュールをサポートする。 最大$n=8$の顧客と$K=3$の車両を持つインスタンス上では、厳密な状態ベクトルシミュレーションにより、目標関数の評価を著しく少なくすることで、低コストソリューションへのコンバージェンスの改善が示され、問題のサイズが増加するにつれて利点が広がる。 これらの結果は、制約された組合せ空間を最適化するための有望なツールとして、構造化された積空間ウォークを同定する。

関連論文リスト

• Quantum iterative approach to the Traveling Salesman Problem [0.6741942263052466]
  トラベリングセールスマン問題(TSP)は、最適化における古典的なNPハード問題であり、問題の規模が大きくなるにつれて、一組の都市で最短ルートを決定することは、計算的に禁止される。 この研究は、この複雑さに対処するための代替アプローチとして量子コンピューティングを探求する。 経路コストは量子位相として符号化され、QPEはそれらを効率的に評価できる一方、振幅増幅はGrover-Longアルゴリズムによって実装され、最適経路に向けた解空間を反復的に洗練する。
  論文  参考訳（メタデータ） (2026-06-10T09:21:15Z)
• Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization [0.7009487789080343]
  複雑な量子回路を近似する枠組みとして, アンシラフリーなユニタリ結合(LCU)について検討する。 フーリエに基づくLCU構造は, 対角および非対角ユニタリの広いクラスを効率的に分解することを示した。
  論文  参考訳（メタデータ） (2026-05-18T18:05:08Z)
• Hybrid Quantum-Classical Optimization Workflows for the Shipment Selection Problem [0.25457638766329743]
  本稿では,IonQとEinrideが共同開発した電気貨物輸送における船積み選択問題(SSP)の量子最適化フレームワークを提案する。 混合整数二次計画としてSSPを定式化し、それをイテレーティブQAOAを用いてイテレーショナルコストハミルトンに写像する。 エンドツーエンドのハイブリッドワークフローは、Einrideの車両ルーティング問題解決とIonQの量子シミュレーションを統合し、130キュービットまでの実際の匿名化ロジスティクスデータの評価を可能にする。
  論文  参考訳（メタデータ） (2026-04-13T17:30:49Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  分散量子最適化のための構造認識フレームワークを提案する。 検索スペースが$N$の場合、我々のフレームワークはプロセッサやセパレータに依存した要素に対して$O(sqrtN)$クエリ複雑性を達成する。 構造を考慮した分解は、量子ネットワーク上でのスケーラブルな分散量子最適化に実践的な道をもたらすことを示す。
  論文  参考訳（メタデータ） (2026-03-08T15:15:52Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。 本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。 また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
  論文  参考訳（メタデータ） (2024-04-17T11:00:12Z)
• Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization [43.74656748515853]
  非定常多重ブロック双レベル最適化問題には$mgg 1$低レベル問題があり、機械学習において重要な応用がある。 a)標準BO問題の最先端の複雑さを1ブロックに合わせること,(b)サンプルブロックごとのサンプルをサンプリングして並列高速化すること,(c)高次元ヘッセン行列推定器の逆計算を避けること,の3つの特性を実現することを目的とする。
  論文  参考訳（メタデータ） (2023-05-30T04:10:11Z)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  異種車両ルーティング問題に対する近似解を求めるために,量子コンピュータの可能性を検討する。 このマッピングに必要なキュービットの数は、顧客数と2倍にスケールすることがわかった。
  論文  参考訳（メタデータ） (2021-10-13T15:38:25Z)
• Quantum walk-based vehicle routing optimisation [0.0]
  本稿では、静電容量化車両ルーティング問題(CVRP)に対する量子ウォークに基づく最適化アルゴリズムの適用性を示す。 効率的なアルゴリズムは、解空間のインデックス化と非インデックス化のために開発され、必要な交互相ウォークのユニタリを実装するために開発された。 QWOAは, ランダムに生成する8つの位置CVRPに対して, ほぼ最適解に収束できるという数値シミュレーション結果を得た。
  論文  参考訳（メタデータ） (2021-09-30T08:04:58Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
  論文  参考訳（メタデータ） (2021-08-03T17:49:09Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)

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

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