Fugu-MT 論文翻訳(概要): A Greedy Quantum Route-Generation Algorithm

論文の概要: A Greedy Quantum Route-Generation Algorithm

arxiv url: http://arxiv.org/abs/2405.03054v1
Date: Sun, 5 May 2024 21:20:46 GMT
ステータス: 処理完了
システム内更新日: 2024-05-07 15:24:13.326685
Title: A Greedy Quantum Route-Generation Algorithm
Title（参考訳）: グレディ量子経路生成アルゴリズム
Authors: Jordan Makansi,
Abstract要約: 本稿では,量子コンピュータから得られた全てのサンプルからの情報を用いて,経路を生成するグリーディアルゴリズムを提案する。有向非巡回グラフ (DAG) としての定式化における量子ビットの関係に気付き, 実現可能な解を適応的に構築するアルゴリズムを設計した。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Routing and scheduling problems with time windows have long been important optimization problems for logistics and planning. Many classical heuristics and exact methods exist for such problems. However, there are no satisfactory methods for generating routes using quantum computing (QC), for mainly two reasons: inequality constraints, and the trade-off of feasibility and solution quality. Inequality constraints are typically handled using slack variables; and feasible solutions are found by filtering samples. These challenges are amplified in the presence of noise inherent in QC. Here, we propose a greedy algorithm that generates routes by using information from all samples obtained from the quantum computer. By noticing the relationship between qubits in our formulation as a directed acyclic graph (DAG), we designed an algorithm that adaptively constructs a feasible solution. We prove its convergence to a feasible solution, and illustrate its efficacy by solving the Fleet Sizing Vehicle Routing Problem with Time Windows (FSVRPTW). Our computational results show that this method obtains a lower objective value than the current state-of-the-art annealing approaches, both classical and hybrid, for the same amount of time using D-Wave Hybrid Solvers. We also show its robustness to noise on D-Wave Advantage 4.1 through computational results as compared to the filtering approach on DWaveSampler, even when the filtering approach is given a longer annealing time, and a larger sample size.
Abstract（参考訳）: 時間窓によるルーティングとスケジューリングの問題は、長年、物流と計画にとって重要な最適化問題であった。多くの古典的ヒューリスティックや正確な方法が存在する。しかし、量子コンピューティング(QC)を用いたルート生成には、主に不等式制約と実現可能性のトレードオフとソリューション品質の2つの理由から満足できる方法がない。不等式制約は通常、スラック変数を使用して処理される。これらの課題は、QC固有のノイズの存在において増幅される。本稿では、量子コンピュータから得られた全てのサンプルから情報を用いて経路を生成するグリージーアルゴリズムを提案する。有向非巡回グラフ (DAG) としての定式化における量子ビットの関係に気付き, 実現可能な解を適応的に構築するアルゴリズムを設計した。本研究では,Fleet Size Vehicle Routing Problem with Time Windows (FSVRPTW) を解くことで,実現可能なソリューションへの収束性を証明し,その有効性を示す。計算結果から,本手法は,D-Wave Hybrid Solvers を用いて,古典的,ハイブリッド的,最先端のアニール法よりも低い目的値が得られることがわかった。また,DWaveSampler のフィルタ手法と比較して,D-Wave Advantage 4.1 の雑音に対する頑健性を示す。

関連論文リスト

Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
量子計算カラーブルーを用いて解くのに適した二次非拘束バイナリ最適化(QUBO)問題を定式化する。この定式化は、最大自己充足力とそれらの間を流れる最小限のパワーを持つコミュニティを見つけることを目的としている。 D-Waveのハイブリッド量子古典解法、古典解法、分枝結合解法などである。
論文参考訳（メタデータ） (2024-07-09T11:44:58Z)
Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCは研究関心の問題を実装でき、コンピュータビジョンタスクのための量子表現の開発に拍車をかけた。本研究では,この情報を確率的バランスの取れたk平均クラスタリングに活用する可能性について検討する。最適でない解を捨てる代わりに, 計算コストを少なくして, 校正後部確率を計算することを提案する。これにより、合成タスクと実際の視覚データについて、D-Wave AQCで示すような曖昧な解とデータポイントを識別することができる。
論文参考訳（メタデータ） (2023-10-18T17:59:45Z)
Towards Finding an Optimal Flight Gate Assignment on a Digital Quantum Computer [0.3324986723090369]
最適飛行ゲート割り当て問題に対する変分量子固有解器(VQE)の性能について検討する。提案手法は,高い確率で優れた解を求めることができることを示す。我々は, エンタングルメントの役割について検討し, エンタングルゲートに接することで, 純粋な製品状態よりも優れた結果が得られることを示す。
論文参考訳（メタデータ） (2023-02-22T19:00:12Z)
Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
論文参考訳（メタデータ） (2023-02-13T19:57:17Z)
Optimization of Robot Trajectory Planning with Nature-Inspired and Hybrid Quantum Algorithms [0.0]
産業規模でロボット軌道計画問題を解く。我々のエンドツーエンドソリューションは、高度に多目的なランダムキーアルゴリズムとモデル積み重ねとアンサンブル技術を統合している。我々は、後者が我々のより大きなパイプラインにどのように統合され、問題に対する量子対応ハイブリッドソリューションを提供するかを示す。
論文参考訳（メタデータ） (2022-06-08T02:38:32Z)
Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文参考訳（メタデータ） (2022-02-17T18:59:20Z)
Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文参考訳（メタデータ） (2021-05-06T17:59:38Z)
Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
線形制約は、量子アニールで表現できる問題のサイズを減らす。オーゼキ法により得られた解に対して,後処理ビットフリップアルゴリズムを適用し,スパースQAPの解法を提案する。 D-Wave Advantage を用いて,D-Wave Advantage を用いた QAP の高精度化に成功した。
論文参考訳（メタデータ） (2020-12-18T09:48:28Z)
TIGER: Topology-aware Assignment using Ising machines Application to Classical Algorithm Tasks and Quantum Circuit Gates [2.4047296366832307]
ゲートベースの量子コンピューティングでは、トポロジー的な方法でタスクをゲートにマップすることを目的とするマッピング問題が存在する。既存のタスクアプローチは、物理最適化アルゴリズムのいずれかに基づいており、異なるスピードとソリューション品質のトレードオフを提供する。本稿では,Ising マシンを用いてトポロジ対応の代入問題を解くアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-09-21T19:46:59Z)
Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文参考訳（メタデータ） (2020-07-14T12:38:21Z)
Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
論文参考訳（メタデータ） (2020-01-12T15:54:20Z)

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

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