論文の概要: Hybrid Quantum-Classical Heuristic for the Bin Packing Problem
- arxiv url: http://arxiv.org/abs/2204.05637v1
- Date: Tue, 12 Apr 2022 09:05:27 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 05:42:43.175709
- Title: Hybrid Quantum-Classical Heuristic for the Bin Packing Problem
- Title(参考訳): ビンパッキング問題に対するハイブリッド量子古典的ヒューリスティック
- Authors: Mikel Garcia de Andoin, Eneko Osaba, Izaskun Oregi, Esther
Villar-Rodriguez, Mikel Sanz
- Abstract要約: 1次元Bin Packing Problem (1dBPP) を扱うためのハイブリッド古典量子法を提案する。
古典的な計算サブルーチンは、量子サブルーチンによって与えられる部分集合から問題に対する完全な解を構築する。
ハイブリッドな解法として、我々はH-BPPと呼ぶ。
- 参考スコア(独自算出の注目度): 0.8434687648198277
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Optimization problems is one of the most challenging applications of quantum
computers, as well as one of the most relevants. As a consequence, it has
attracted huge efforts to obtain a speedup over classical algorithms using
quantum resources. Up to now, many problems of different nature have been
addressed through the perspective of this revolutionary computation paradigm,
but there are still many open questions. In this work, a hybrid
classical-quantum approach is presented for dealing with the one-dimensional
Bin Packing Problem (1dBPP). The algorithm comprises two modules, each one
designed for being executed in different computational ecosystems. First, a
quantum subroutine seeks a set of feasible bin configurations of the problem at
hand. Secondly, a classical computation subroutine builds complete solutions to
the problem from the subsets given by the quantum subroutine. Being a hybrid
solver, we have called our method H-BPP. To test our algorithm, we have built
18 different 1dBPP instances as a benchmarking set, in which we analyse the
fitness, the number of solutions and the performance of the QC subroutine.
Based on these figures of merit we verify that H-BPP is a valid technique to
address the 1dBPP.
- Abstract(参考訳): 最適化問題は量子コンピュータの最も困難な応用の1つであり、最も関連する分野の1つである。
その結果、量子資源を用いた古典的アルゴリズムの高速化に多大な努力を払っている。
これまで、様々な性質の問題は、この革命的計算パラダイムの見地から取り組まれてきたが、まだ多くの疑問が残されている。
本研究では, 1次元Bin Packing Problem (1dBPP) を扱うための古典量子ハイブリッド手法を提案する。
アルゴリズムは2つのモジュールで構成され、それぞれ異なる計算エコシステムで実行されるよう設計されている。
まず、量子サブルーチンは、手元にある問題の実行可能なビン構成のセットを求める。
第二に、古典的な計算サブルーチンは、量子サブルーチンによって与えられる部分集合から問題に対する完全な解を構築する。
ハイブリッドな解法として、我々はH-BPPと呼ぶ。
アルゴリズムをテストするため,ベンチマークセットとして18種類の1dBPPインスタンスを構築し,適合度,解数,QCサブルーチンの性能を解析した。
これらの評価値に基づいて、H-BPPが1dBPPに対処する有効な手法であることを検証する。
関連論文リスト
- Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms [0.0]
組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。
この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
論文 参考訳(メタデータ) (2024-03-05T17:46:04Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳(メタデータ) (2023-11-07T04:59:02Z) - Quantum-based Distributed Algorithms for Edge Node Placement and
Workload Allocation [8.937905773981702]
最適なエッジサーバ配置とワークロード割り当てのための混合整数線形プログラミング(MILP)モデルを提案する。
既存の量子解法は制約のないバイナリプログラミング問題の解法に限られる。
数値実験により,エッジコンピューティングの複雑な最適化問題を解くために量子超越性を活用できることが実証された。
論文 参考訳(メタデータ) (2023-06-01T21:33:08Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
Bin Packing Problem (BPP) は、ロジスティクスにおけるパラダイム最適化問題として際立っている。
我々は最近,一次元BPPに対するハイブリッドアプローチを提案している。
他の古典的手法と比較する。
論文 参考訳(メタデータ) (2022-07-15T13:09:12Z) - Classically-Boosted Quantum Optimization Algorithm [0.0]
我々は、量子最適化を強化するために既存の古典的手法を活用する自然なアプローチを探求する。
具体的には、近似解を見つけるために古典的なアルゴリズムを実行し、量子回路を用いて高品質な解の「近傍」を探索する。
CBQOA の Max 3SAT および Max Bisection への応用を実証し,これらの問題に対する従来のアプローチよりも優れていることを示す実証的証拠を提供する。
論文 参考訳(メタデータ) (2022-03-25T23:36:14Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳(メタデータ) (2022-01-25T05:59:24Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳(メタデータ) (2021-07-08T17:59:55Z) - 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) - Focusing on the Hybrid Quantum Computing -- Tabu Search Algorithm: new
results on the Asymmetric Salesman Problem [1.672938048065882]
本稿では,分割問題に対するハイブリッド量子コンピューティング - Tabu Search Algorithm の結果と結果を拡張する。
さらなる貢献として、この研究は量子コンピューティングを用いた非対称トラベリングセールスマン問題の最初の解法であると仮定する。
論文 参考訳(メタデータ) (2021-02-11T10:08:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。