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

• arxiv url: http://arxiv.org/abs/2306.08507v1
• Date: Wed, 14 Jun 2023 13:44:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-16 18:47:36.056086
• Title: Qubit efficient quantum algorithms for the vehicle routing problem on quantum computers of the NISQ era
• Title（参考訳）: NISQ時代の量子コンピュータにおける車両ルーティング問題に対する量子ビット効率的な量子アルゴリズム
• Authors: Ioannis D. Leonidas, Alexander Dukakis, Benjamin Tan, Dimitris G. Angelakis
• Abstract要約: 時間窓付き車両ルーティング問題(VRPTW)は、ロジスティクスや輸送など、多くの分野で発生する古典的な最適化問題である。 本研究では、QUBOとしてVRPTWを定式化し、提案した符号化方式を用いて、VRPTWに量子変分アプローチを適用する。 提案手法は,全符号化を用いた量子アルゴリズムの解に匹敵するVRPTWの近似解を求めることができることを示す。
• 参考スコア（独自算出の注目度）: 65.31857472429745
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The vehicle routing problem with time windows (VRPTW) is a classic optimization problem that arises in many different areas, such as logistics and transportation. The goal of the VRPTW is to find the shortest possible route for a fleet of vehicles to visit a set of destinations. In recent years, there has been growing interest in using variational quantum algorithms (VQAs), to find approximate solutions to problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. In this work, we formulate the VRPTW as a QUBO and apply a quantum variational approach to the VRPTW using our earlier suggested encoding scheme described in [1] to reduce drastically the number of qubits required. We evaluate our approach on a set of VRPTW instances ranging from 11 to 3964 routes constructed with data provided by researchers from ExxonMobil. We compare the solutions obtained with standard full encoding approaches for which the max problems size possible in NISQ era are of the order of 20-30 routes. We run our algorithms in simulators as well as cloud quantum hardware provided by IBMQ, AWS (Rigetti) and IonQ and benchmark our results against each other as well as on the simulators. We show that our approach can find approximate solutions to the VRPTW that are comparable to the solutions found by quantum algorithms using the full encoding. Our results suggest that our unique encoding approach, provides a promising approach to drastically reducing the number of qubits required to find decent approximate solutions for industry-based optimization problems.
• Abstract（参考訳）: タイムウインドウ(VRPTW)による車両ルーティング問題は、ロジスティクスや輸送など、多くの分野で発生する古典的な最適化問題である。 VRPTWの目標は、車両群が目的地を訪れるための最短ルートを見つけることである。 近年,2次非制約バイナリ最適化(QUBO)問題として定式化できる問題に対する近似解を求めるために,変分量子アルゴリズム(VQA)の使用への関心が高まっている。 本研究では,vrptw を qubo として定式化し,[1] に記述した先述の符号化方式を用いて vrptw に量子変分法を適用し,必要な qubit 数を大幅に削減する。 exxonmobilの研究者が提供したデータをもとに,11～3964経路のvrptwインスタンスを対象に,提案手法を評価した。 NISQ時代に可能な最大問題のサイズが20-30経路の順序であるような標準的な完全符号化手法を用いて得られた解を比較した。 ibmq、aws(rigetti)、ionqによって提供されるクラウド量子ハードウェアだけでなく、シミュレータでアルゴリズムを実行し、シミュレータ上でも結果をベンチマークします。 本手法は,全エンコーディングを用いた量子アルゴリズムの解に匹敵するvrptwの近似解を求めることができることを示す。 その結果,業界毎の最適化問題に対する近似解を求めるのに必要な量子ビット数を劇的に削減する有望な手法が提案されている。

関連論文リスト

• 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)

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

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