論文の概要: Quantum Computing for a Profusion of Postman Problem Variants
- arxiv url: http://arxiv.org/abs/2208.08397v1
- Date: Wed, 17 Aug 2022 16:42:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-30 20:09:45.732554
- Title: Quantum Computing for a Profusion of Postman Problem Variants
- Title(参考訳): ポストマン問題変数の拡散に対する量子計算
- Authors: Joel E. Pion, Christian F. A. Negre, Susan M. Mniszewski
- Abstract要約: グラフルーティング最適化問題である中国語ポストマン問題を解くことの実現可能性について検討する。
本稿では,これらの問題を2次的制約のない二項最適化問題に変換する方法の説明に重点を置いている。
また,未方向閉グラフ上での中国語ポストマン問題の解法についても検討した。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In this paper we study the viability of solving the Chinese Postman Problem,
a graph routing optimization problem, and many of its variants on a quantum
annealing device. Routing problem variants considered include graph type,
directionally varying weights, number of parties involved in routing, among
others. We put emphasis on the explanation of how to convert such problems into
quadratic unconstrained binary optimization (QUBO) problems, one of two
equivalent natural paradigms for quantum annealing devices. We also expand upon
a previously discovered algorithm for solving the Chinese Postman Problem on a
closed undirected graph to decrease the number of constraints and variables
used in the problem. Optimal annealing parameter settings and constraint weight
values are discussed based on results from implementation on the D-Wave 2000Q
and Advantage. Results from classical, purely quantum, and hybrid algorithms
are compared.
- Abstract(参考訳): 本稿では,中国のポストマン問題,グラフルーティング最適化問題,および量子アニールデバイス上での多くの変種を解くことの実現可能性について検討する。
ルーティングの問題には、グラフタイプ、方向によって異なる重み、ルーティングに関わるパーティの数などが含まれる。
本稿では,これらの問題を量子アニールデバイスに等価な2つの自然パラダイムの1つである2次非制約バイナリ最適化(QUBO)問題に変換する方法について述べる。
また,中国のポストマン問題を非直交グラフ上で解くアルゴリズムを拡張し,その問題に使用する制約や変数の数を削減した。
D-Wave 2000QとAdvantageの実装結果に基づいて最適アニールパラメータ設定と制約重み値について議論する。
古典的アルゴリズム、純粋量子アルゴリズム、ハイブリッドアルゴリズムの結果を比較する。
関連論文リスト
- Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳(メタデータ) (2023-11-16T09:19:01Z) - Quantum Optimization: Lagrangian Dual versus QUBO in Solving Constrained
Problems [0.0]
本稿では,ラグランジアン双対性の概念を離散化された断熱量子計算の枠組みに組み込むことにより,制約付き最適化問題の解法を提案する。
回路モデル-フォールトトレラント量子計算の設定において,本手法が回路深さの2次改善を実現し,制約に依存しない回路幅を維持できることを示す。
論文 参考訳(メタデータ) (2023-10-06T19:09:55Z) - Improving Performance in Combinatorial Optimization Problems with
Inequality Constraints: An Evaluation of the Unbalanced Penalization Method
on D-Wave Advantage [0.0]
非バランスなペナル化と呼ばれる新しい手法が、スラック変数の使用を避けるために提案されている。
本研究は、旅行セールスマン問題(TSP)に対するD-Wave Advantage上の実量子ハードウェアを用いた不均衡ペナル化法をテストする。
その結果、不均衡なペナル化法はスラック変数を用いた解よりも優れていた。
論文 参考訳(メタデータ) (2023-05-30T05:40:50Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳(メタデータ) (2022-11-01T07:52:47Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳(メタデータ) (2021-06-11T09:43:09Z) - 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) - Investigating the Chinese Postman Problem on a Quantum Annealer [0.0]
D-Waveアナライザは、二次的制約のないバイナリ最適化という形で問題を解決することを約束するプラットフォームである。
グラフやネットワークの局所接続を探索するためのツールとして使用できる,中国のポストマン問題の定式化について述べる。
論文 参考訳(メタデータ) (2020-08-06T17:11:54Z) - Modeling Linear Inequality Constraints in Quadratic Binary Optimization
for Variational Quantum Eigensolver [0.0]
本稿では, 変分量子固有解法における配向型変分形式の利用について紹介する。
通常、いくつかの最適化問題に現れる4つの制約がモデル化されている。
提案手法の主な利点は、変分形式のパラメータの数が一定であることである。
論文 参考訳(メタデータ) (2020-07-26T23:36:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。