論文の概要: Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing
Problem
- arxiv url: http://arxiv.org/abs/2304.09629v2
- Date: Sun, 7 May 2023 16:09:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-09 20:27:15.018219
- Title: Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing
Problem
- Title(参考訳): 容量型車両経路問題に対する量子支援解経路
- Authors: Lilly Palackal, Benedikt Poggel, Matthias Wulff, Hans Ehm, Jeanette
Miriam Lorenz, Christian B. Mendl
- Abstract要約: 我々は、キャパシタントカー問題(CVRP)またはその減量版であるトラベリングセールスパーソン問題(TSP)について議論する。
今日の最も強力な古典的アルゴリズムでさえ、CVRPは古典的解決が難しい。
量子コンピューティングは、ソリューションの時間を改善する手段を提供するかもしれない。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many relevant problems in industrial settings result in NP-hard optimization
problems, such as the Capacitated Vehicle Routing Problem (CVRP) or its reduced
variant, the Travelling Salesperson Problem (TSP). Even with today's most
powerful classical algorithms, the CVRP is challenging to solve classically.
Quantum computing may offer a way to improve the time to solution, although the
question remains open as to whether Noisy Intermediate-Scale Quantum (NISQ)
devices can achieve a practical advantage compared to classical heuristics. The
most prominent algorithms proposed to solve combinatorial optimization problems
in the NISQ era are the Quantum Approximate Optimization Algorithm (QAOA) and
the more general Variational Quantum Eigensolver (VQE). However, implementing
them in a way that reliably provides high-quality solutions is challenging,
even for toy examples. In this work, we discuss decomposition and formulation
aspects of the CVRP and propose an application-driven way to measure solution
quality. Considering current hardware constraints, we reduce the CVRP to a
clustering phase and a set of TSPs. For the TSP, we extensively test both QAOA
and VQE and investigate the influence of various hyperparameters, such as the
classical optimizer choice and strength of constraint penalization. Results of
QAOA are generally of limited quality because the algorithm does not reach the
energy threshold for feasible TSP solutions, even when considering various
extensions such as recursive, warm-start and constraint-preserving mixer QAOA.
On the other hand, the VQE reaches the energy threshold and shows a better
performance. Our work outlines the obstacles to quantum-assisted solutions for
real-world optimization problems and proposes perspectives on how to overcome
them.
- Abstract(参考訳): 産業環境における多くの関連する問題は、CVRP(Capacitated Vehicle Routing Problem)やTSP(Travelling Salesperson Problem)といったNPハード最適化の問題をもたらす。
今日の最も強力な古典的アルゴリズムでさえ、CVRPは古典的解決が難しい。
量子コンピューティングは解法を改善する方法を提供するかもしれないが、ノイズ中間スケール量子(NISQ)デバイスが古典的ヒューリスティックよりも実用的な優位性が得られるかどうかについては未解決のままである。
NISQ時代の組合せ最適化問題を解くために提案された最も顕著なアルゴリズムは、量子近似最適化アルゴリズム(QAOA)とより一般的な変分量子固有解法(VQE)である。
しかし、おもちゃの例であっても、高品質なソリューションを確実に提供する方法で実装することは難しい。
本稿では,CVRPの分解と定式化について論じ,ソリューションの品質を計測するアプリケーション駆動手法を提案する。
現在のハードウェア制約を考慮すると、CVRPをクラスタリングフェーズとTSPのセットに還元する。
TSPでは、QAOAとVQEの両方を広範囲にテストし、古典的なオプティマイザ選択や制約ペナライゼーションの強度など、様々なハイパーパラメータの影響について検討する。
QAOAの結果は、再帰的、ウォームスタート、制約保存ミキサーQAOAといった様々な拡張を考慮しても、アルゴリズムが実現可能なTSPソリューションのエネルギーしきい値に達しないため、一般的に限られた品質である。
一方、VQEはエネルギー閾値に達し、より良い性能を示す。
本研究は,実世界の最適化問題に対する量子支援解への障害を概説し,その克服方法についての展望を提案する。
関連論文リスト
- A joint optimization approach of parameterized quantum circuits with a
tensor network [0.0]
現在の中間スケール量子(NISQ)デバイスはその能力に制限がある。
本稿では,パラメータ化ネットワーク(TN)を用いて,変分量子固有解法(VQE)アルゴリズムの性能改善を試みる。
論文 参考訳(メタデータ) (2024-02-19T12:53:52Z) - Multi-objective Quantum Annealing approach for solving flexible job shop
scheduling in manufacturing [0.0]
本稿では、フレキシブルジョブショップスケジューリング問題に対処するため、量子アニーリングに基づく問題解決アルゴリズム(QASA)を提案する。
ベンチマーク問題の実験では、タブ検索、シミュレートされたアニーリング、量子アニーリングを組み合わせたQASAが、古典的解法アルゴリズム(CSA)のソリューション品質を上回っている。
論文 参考訳(メタデータ) (2023-11-16T07:45:57Z) - Challenges of variational quantum optimization with measurement shot
noise [0.0]
問題の大きさが大きくなるにつれて、量子資源のスケーリングが一定の成功確率に達するか検討する。
この結果から,ハイブリッド量子古典アルゴリズムは古典外ループの破壊力を回避する必要がある可能性が示唆された。
論文 参考訳(メタデータ) (2023-07-31T18:01:15Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳(メタデータ) (2023-06-15T15:28:12Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - Fermionic Quantum Approximate Optimization Algorithm [11.00442581946026]
制約付き最適化問題を解くためのフェルミオン量子近似最適化アルゴリズム(FQAOA)を提案する。
FQAOAは、フェルミオン粒子数保存を用いて、QAOAを通して本質的にそれらを強制する制約問題に対処する。
制約付きハミルトニアン問題に対して、運転者ハミルトニアンを設計するための体系的なガイドラインを提供する。
論文 参考訳(メタデータ) (2023-01-25T18:36:58Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Analysis of Vehicle Routing Problem in Presence of Noisy Channels [0.0]
車両ルーティング問題(VRP)はNPハード最適化問題である。
この研究は、変数 ANSATZ 上の変分量子固有解法を用いて、3 と 4 の都市に基本的な VRP ソリューションを構築する。
論文 参考訳(メタデータ) (2021-12-28T10:20:42Z) - Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
本稿では、QAS(Quantum Architecture Search)と呼ばれるリソースと実行時の効率的なスキームを提案する。
QASは、よりノイズの多い量子ゲートを追加することで得られる利点と副作用のバランスをとるために、自動的にほぼ最適アンサッツを求める。
数値シミュレータと実量子ハードウェアの両方に、IBMクラウドを介してQASを実装し、データ分類と量子化学タスクを実現する。
論文 参考訳(メタデータ) (2020-10-20T12:06:27Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。