論文の概要: Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors

• arxiv url: http://arxiv.org/abs/2306.08507v2
• Date: Tue, 19 Sep 2023 14:09:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-20 19:40:24.303401
• Title: Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors
• Title（参考訳）: NISQプロセッサ上の車両ルーティング問題に対する量子量子ビットアルゴリズム
• Authors: Ioannis D. Leonidas, Alexander Dukakis, Benjamin Tan, Dimitris G. Angelakis
• Abstract要約: 時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクス業界で直面する一般的な最適化問題である。 そこで本研究では,以前に導入した量子ビット符号化方式を用いて,バイナリ変数の数を削減した。
• 参考スコア（独自算出の注目度）: 48.68474702382697
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables, to evaluate the effectiveness of NISQ devices when applied to industry relevant optimization problems. We apply a quantum variational approach to a testbed of multiple VRPTW instances ranging from 11 to 3964 routes. These intances were formulated as quadratic unconstrained binary optimization (QUBO) problems based on realistic shipping scenarios. We compare our results with standard binary-to-qubit mappings after executing on simulators as well as various quantum hardware platforms, including IBMQ, AWS (Rigetti), and IonQ. These results are benchmarked against the classical solver, Gurobi. Our approach can find approximate solutions to the VRPTW comparable to those obtained from quantum algorithms using the full encoding, despite the reduction in qubits required. These results suggest that using the encoding scheme to fit larger problem sizes into fewer qubits is a promising step in using NISQ devices to find approximate solutions for industry-based optimization problems, although additional resources are still required to eke out the performance from larger problem sizes.
• Abstract（参考訳）: 時間窓付き車両ルーティング問題(VRPTW)は、物流業界で直面する一般的な最適化問題である。 本研究では,従来導入されていた量子ビット符号化方式を用いてバイナリ変数数を削減し,業界関連の最適化問題に適用した場合のNISQデバイスの有効性を評価する。 我々は、11から3964ルートの複数のVRPTWインスタンスのテストベッドに量子変分法を適用した。 これらの命令は、現実的な出荷シナリオに基づいた2次非制約バイナリ最適化(QUBO)問題として定式化された。 ibmq、aws(rigetti)、ionqなど様々な量子ハードウェアプラットフォームに加えて、シミュレータ上で実行した後の標準的なバイナリ-量子ビットマッピングと比較した。 これらの結果は古典的な解法であるグロビに対してベンチマークされる。 本手法は、量子ビットの削減に拘わらず、全エンコーディングを用いて量子アルゴリズムから得られるものに匹敵するvrptwの近似解を求めることができる。 これらの結果から,より大規模な問題サイズを少ないキュービットに適合させるエンコーディング方式は,NISQデバイスを用いて産業最適化問題の近似解を求める上で有望なステップであることが示された。

関連論文リスト

• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  変分量子アルゴリズム(VQA)は、最適化と機械学習問題を解決するための有望な量子代替手段として登場した。 本稿では,回路設計が2つの分類問題に対して得られる性能に与える影響を実験的に示す。 また、実量子コンピュータのシミュレーションにおいて、ノイズの存在下で得られた回路の劣化について検討する。
  論文  参考訳（メタデータ） (2024-04-17T11:00:12Z)
• Improving Quantum and Classical Decomposition Methods for Vehicle Routing [2.4646794072984477]
  本稿では,2つの分解法,すなわちグラフ縮小と回路切断の精巧な組み合わせを提案する。 この結果から,現在の量子技術の制約内での最適化問題に対するアルゴリズムの性能に関する知見が得られた。
  論文  参考訳（メタデータ） (2024-04-08T14:19:25Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。 問題の大きさと問題グラフの次数で指数関数的に増大する。 これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
  論文  参考訳（メタデータ） (2022-01-06T21:02:30Z)
• Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
  車両ルーティング問題(VRP)はNPハード最適化問題である。 この研究は、変数 ANSATZ 上の変分量子固有解法を用いて、3 と 4 の都市に基本的な VRP ソリューションを構築する。
  論文  参考訳（メタデータ） (2021-12-28T10:20:42Z)
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem [0.7503129292751939]
  異種車両ルーティング問題に対する近似解を求めるために,量子コンピュータの可能性を検討する。 このマッピングに必要なキュービットの数は、顧客数と2倍にスケールすることがわかった。
  論文  参考訳（メタデータ） (2021-10-13T15:38:25Z)
• 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)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  変分量子アルゴリズム(VQA)は、特定の計算上の利点を得るために、短期量子マシンを利用する可能性がある。 現代のVQAは、巨大なデータを扱うために単独の量子プロセッサを使用するという伝統によって妨げられている、計算上のオーバーヘッドに悩まされている。 ここでは、この問題に対処するため、効率的な分散最適化手法であるQUDIOを考案する。
  論文  参考訳（メタデータ） (2021-06-24T08:18:42Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)

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

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