論文の概要: 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に対処する有効な手法であることを検証する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Bayesian Optimization Priors for Efficient Variational Quantum Algorithms [0.0]
量子コンピュータは現在、量子量子アルゴリズム(VQA)と呼ばれる量子古典的なアプローチで問題を解決している。
本稿では,時間当たりのショット数を削減できる基本計算最適化のためのハイブリッドフレームワークを提案する。
この2つの特徴を用いて,提案手法がVQA内でのシミュレーション実装を統計的に上回っていることを示す。
論文 参考訳（メタデータ） (2024-06-20T18:00:12Z) - A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
本稿では,量子安定化器符号の最小距離を準拘束的二項最適化問題として再定式化することで計算する手法を提案する。
D-Wave Advantage 4.1quantum annealerと比較することにより,本手法の実用性を示す。
論文 参考訳（メタデータ） (2024-04-26T21:29:42Z) - Solving non-native combinatorial optimization problems using hybrid
quantum-classical algorithms [0.0]
組合せ最適化は、物流から金融まで幅広い分野に適用可能な、困難な問題である。
量子コンピューティングは、様々なアルゴリズムを用いてこれらの問題を解決するために使われてきた。
この研究は、量子と古典のリソースをハイブリッドなアプローチで統合することで、これらの課題を克服する枠組みを提示している。
論文 参考訳（メタデータ） (2024-03-05T17:46:04Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。