論文の概要: Unconstrained Binary Models of the Travelling Salesman Problem Variants
for Quantum Optimization
- arxiv url: http://arxiv.org/abs/2106.09056v2
- Date: Tue, 28 Dec 2021 09:54:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-26 12:59:50.201544
- Title: Unconstrained Binary Models of the Travelling Salesman Problem Variants
for Quantum Optimization
- Title（参考訳）: 量子最適化のための巡回セールスマン問題の非拘束二元モデル
- Authors: \"Ozlem Salehi, Adam Glos, Jaros{\l}aw Adam Miszczak
- Abstract要約: 本稿では,Travelling Salesman Problem with Time Windows (TSPTW) の量子コンピュータ上での解法を詳細に分析する。
本稿では、制約のない二項最適化と高階二項最適化の定式化を導入する。
TSPTW問題のエッジベースおよびノードベースの定式化の利点を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum computing is offering a novel perspective for solving combinatorial
optimization problems. To fully explore the possibilities offered by quantum
computers, the problems need to be formulated as unconstrained binary models,
taking into account limitation and advantages of quantum devices. In this work,
we provide a detailed analysis of the Travelling Salesman Problem with Time
Windows (TSPTW) in the context of solving it on a quantum computer. We
introduce quadratic unconstrained binary optimization and higher order binary
optimization formulations of this problem. We demonstrate the advantages of
edge-based and node-based formulations of the TSPTW problem. Additionally, we
investigate the experimental realization of the presented methods on a quantum
annealing device. The provided results pave the path for utilizing quantum
computer for a variety of real-world task which can be cast in the form of
Travelling Salesman Problem with Time Windows problem.
- Abstract（参考訳）: 量子コンピューティングは組合せ最適化問題を解決する新しい視点を提供する。
量子コンピュータがもたらす可能性を完全に探求するには、量子デバイスの限界と利点を考慮して、制約のないバイナリモデルとして定式化する必要がある。
本研究では,Travelling Salesman Problem with Time Windows (TSPTW) の量子コンピュータ上での解法に関する詳細な解析を行う。
本稿では,2次非拘束二進最適化と高次二進最適化を導入する。
TSPTW問題のエッジベースおよびノードベースの定式化の利点を示す。
さらに, 提案手法の量子アニール装置における実験的実現について検討した。
提案した結果は、Travelling Salesman Problem with Time Windows という形で、様々な現実世界のタスクに量子コンピュータを利用するための道を開くものである。
関連論文リスト
- Quantum-based Distributed Algorithms for Edge Node Placement and
Workload Allocation [8.937905773981702]
最適なエッジサーバ配置とワークロード割り当てのための混合整数線形プログラミング(MILP)モデルを提案する。
既存の量子解法は制約のないバイナリプログラミング問題の解法に限られる。
数値実験により,エッジコンピューティングの複雑な最適化問題を解くために量子超越性を活用できることが実証された。
論文 参考訳（メタデータ） (2023-06-01T21:33:08Z) - Quantum and quantum-inspired optimization for solving the minimum bin
packing problem [0.0]
原子力産業に関係のある深部貯留キャニスターに使用済み核燃料を充填する問題について考察する。
まず、上記の問題を2次非制約バイナリ最適化の観点から再定義する。
本研究は、量子および量子に着想を得た最適化を用いて、原子エネルギー産業の産業関連問題を解く可能性を示す。
論文 参考訳（メタデータ） (2023-01-26T18:04:18Z) - NP-hard but no longer hard to solve? Using quantum computing to tackle
optimization problems [1.1470070927586016]
量子コンピュータを用いて最適化問題を解く量子最適化の分野について論じる。
適切なユースケースを通じてこれを実証し、量子コンピュータの現在の品質について論じる。
本稿では、最近の量子最適化のブレークスルーと現状と今後の方向性について論じる。
論文 参考訳（メタデータ） (2022-12-21T12:56:37Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - Constrained Quantum Optimization for Extractive Summarization on a
Trapped-ion Quantum Computer [13.528362112761805]
本稿では,量子ハードウェアの制約を保存する量子最適化アルゴリズムの,これまでで最大の実行方法を示す。
我々は、最大20キュービットと2キュービットゲート深さ最大159の量子進化を制限するXY-QAOA回路を実行する。
本稿では,アルゴリズムのトレードオフと,短期量子ハードウェア上での実行に対する影響について論じる。
論文 参考訳（メタデータ） (2022-06-13T16:21:04Z) - Efficient Use of Quantum Linear System Algorithms in Interior Point
Methods for Linear Optimization [0.0]
線形最適化問題を解くために、非現実的な量子内点法を開発した。
また、量子ソルバの過度な時間なしで、反復リファインメントによって正確な解を得る方法についても論じる。
論文 参考訳（メタデータ） (2022-05-02T21:30:56Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Quantum Permutation Synchronization [88.4588059792167]
本稿では,コンピュータビジョンの文脈における量子ビジョン問題を解決する量子アルゴリズムQuantumSyncを提案する。
本稿では、QUBO 問題に置換制約を挿入し、アバスティック量子 DWave コンピュータの電流生成に関する制約付き QUBO 問題を解決する方法を示す。
論文 参考訳（メタデータ） (2021-01-19T17:51:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。