論文の概要: QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing
- arxiv url: http://arxiv.org/abs/2309.12678v2
- Date: Mon, 15 Jan 2024 20:10:40 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 01:35:59.956982
- Title: QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing
- Title(参考訳): QAL-BP: ビンパッキングのための拡張ラグランジアン量子アプローチ
- Authors: Lorenzo Cellini, Antonio Macaluso, Michele Lombardi
- Abstract要約: ビンパッキングは人工知能の分野でよく知られたNP-Hard問題である。
量子技術の最近の進歩は、かなりの計算スピードアップを達成するための有望な可能性を示している。
QAL-BPは, ビンパッキングに特化して設計された, 擬似非拘束バイナリ最適化(QUBO)の定式化である。
- 参考スコア(独自算出の注目度): 4.589533935256401
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The bin packing is a well-known NP-Hard problem in the domain of artificial
intelligence, posing significant challenges in finding efficient solutions.
Conversely, recent advancements in quantum technologies have shown promising
potential for achieving substantial computational speedup, particularly in
certain problem classes, such as combinatorial optimization. In this study, we
introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO)
formulation designed specifically for bin packing and suitable for quantum
computation. QAL-BP utilizes the Augmented Lagrangian method to incorporate the
bin packing constraints into the objective function while also facilitating an
analytical estimation of heuristic, but empirically robust, penalty
multipliers. This approach leads to a more versatile and generalizable model
that eliminates the need for empirically calculating instance-dependent
Lagrangian coefficients, a requirement commonly encountered in alternative QUBO
formulations for similar problems. To assess the effectiveness of our proposed
approach, we conduct experiments on a set of bin packing instances using a real
Quantum Annealing device. Additionally, we compare the results with those
obtained from two different classical solvers, namely simulated annealing and
Gurobi. The experimental findings not only confirm the correctness of the
proposed formulation but also demonstrate the potential of quantum computation
in effectively solving the bin packing problem, particularly as more reliable
quantum technology becomes available.
- Abstract(参考訳): ビンパッキングは人工知能の分野でよく知られたNP-Hard問題であり、効率的なソリューションを見つける上で大きな課題となっている。
逆に、量子技術における最近の進歩は、特に組合せ最適化のような特定の問題クラスにおいて、計算の大幅な高速化を達成する可能性を示している。
本研究では, ビンパッキングに特化して設計され, 量子計算に適した新奇な非拘束バイナリ最適化(QUBO)の定式化であるQAL-BPを紹介する。
qal-bpは拡張ラグランジアン法を用いて、ビンパッキング制約を目的関数に組み込むと同時に、ヒューリスティックだが経験的にロバストなペナルティ乗算器の分析的推定も行う。
このアプローチはより汎用的で一般化可能なモデルとなり、類似した問題に対する代替QUBOの定式化でよく見られる、インスタンス依存ラグランジュ係数を経験的に計算する必要がなくなる。
提案手法の有効性を評価するため,実量子アニーリング装置を用いて,ビン包装インスタンスの集合について実験を行った。
さらに, シミュレーションアニーリングとグロビの2種類の古典解法から得られた結果と比較した。
実験結果は,提案手法の正確性を確認するだけでなく,より信頼性の高い量子技術が普及するにつれて,ビンパッキング問題を効果的に解くための量子計算の可能性を示すものである。
関連論文リスト
- Variational quantum eigensolver with linear depth problem-inspired
ansatz for solving portfolio optimization in finance [7.501820750179541]
本稿では,金融におけるポートフォリオ最適化問題を解決するために,変分量子固有解法(VQE)を提案する。
超伝導量子コンピュータWu Kongにおける最大55量子ビットのHDC実験を実装した。
HDCスキームは、NISQ時代に量子アドバンテージを達成する大きな可能性を示している。
論文 参考訳(メタデータ) (2024-03-07T07:45:47Z) - Quantum Optimization: Lagrangian Dual versus QUBO in Solving Constrained
Problems [0.0]
本稿では,ラグランジアン双対性の概念を離散化された断熱量子計算の枠組みに組み込むことにより,制約付き最適化問題の解法を提案する。
回路モデル-フォールトトレラント量子計算の設定において,本手法が回路深さの2次改善を実現し,制約に依存しない回路幅を維持できることを示す。
論文 参考訳(メタデータ) (2023-10-06T19:09:55Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - A Quantum Approach for Stochastic Constrained Binary Optimization [2.6803492658436032]
量子ベースのアルゴリズムは、難しい問題に対する高品質な解を生成することが示されている。
この研究は、二進二乗制約プログラムに対処する量子ベクトルを提示する。
この手法は二重分解に基づいて構築され、規則的に修正された標準VQEタスクの順序を解く必要がある。
論文 参考訳(メタデータ) (2023-01-04T04:24:26Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳(メタデータ) (2022-11-01T07:52:47Z) - Evaluating the Convergence of Tabu Enhanced Hybrid Quantum Optimization [58.720142291102135]
本稿では,量子ハードウェア上での最適化問題解決に有用な Tabu Enhanced Hybrid Quantum Optimization メタヒューリスティック手法を提案する。
提案手法の理論的収束を,イジングモデルに基づくタブ状態を保存する対象の衝突の観点から考察する。
論文 参考訳(メタデータ) (2022-09-05T07:23:03Z) - Constrained Quantum Optimization for Extractive Summarization on a
Trapped-ion Quantum Computer [13.528362112761805]
本稿では,量子ハードウェアの制約を保存する量子最適化アルゴリズムの,これまでで最大の実行方法を示す。
我々は、最大20キュービットと2キュービットゲート深さ最大159の量子進化を制限するXY-QAOA回路を実行する。
本稿では,アルゴリズムのトレードオフと,短期量子ハードウェア上での実行に対する影響について論じる。
論文 参考訳(メタデータ) (2022-06-13T16:21:04Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳(メタデータ) (2021-08-03T17:49: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) - Tabu-driven Quantum Neighborhood Samplers [2.9934511331003555]
組合せ最適化は、量子コンピューティングを対象とする重要なアプリケーションである。
短期的なデバイスで利点を享受する一つの選択肢は、それらを古典と組み合わせて使うことである。
このようなハイブリッド環境において,QAOAはアルゴリズム探索のための柔軟なツールであることを示す。
論文 参考訳(メタデータ) (2020-11-18T19:30:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。