論文の概要: Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem
- arxiv url: http://arxiv.org/abs/2207.07460v1
- Date: Fri, 15 Jul 2022 13:09:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-04 22:59:56.076958
- Title: Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem
- Title（参考訳）: ビン包装問題に対する量子アルゴリズムの比較ベンチマーク
- Authors: Mikel Garcia-de-Andoin, Izaskun Oregi, Esther Villar-Rodriguez, Eneko
Osaba, Mikel Sanz
- Abstract要約: Bin Packing Problem (BPP) は、ロジスティクスにおけるパラダイム最適化問題として際立っている。
我々は最近,一次元BPPに対するハイブリッドアプローチを提案している。
他の古典的手法と比較する。
- 参考スコア（独自算出の注目度）: 0.8434687648198277
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Bin Packing Problem (BPP) stands out as a paradigmatic combinatorial
optimization problem in logistics. Quantum and hybrid quantum-classical
algorithms are expected to show an advantage over their classical counterparts
in obtaining approximate solutions for optimization problems. We have recently
proposed a hybrid approach to the one dimensional BPP in which a quantum
annealing subroutine is employed to sample feasible solutions for single
containers. From this reduced search space, a classical optimization subroutine
can find the solution to the problem. With the aim of going a step further in
the evaluation of our subroutine, in this paper we compare the performance of
our procedure with other classical approaches. Concretely we test a random
sampling and a random-walk-based heuristic. Employing a benchmark comprising 18
instances, we show that the quantum approach lacks the stagnation behaviour
that slows down the classical algorithms. Based on this, we conclude that the
quantum strategy can be employed jointly with the random walk to obtain a full
sample of feasible solutions in fewer iterations. This work improves our
intuition about the benefits of employing the scarce quantum resources to
improve the results of a diminishingly efficient classical strategy.
- Abstract（参考訳）: Bin Packing Problem (BPP) は、物流におけるパラダイム的な組合せ最適化問題である。
量子アルゴリズムとハイブリッド量子古典アルゴリズムは、最適化問題に対する近似解を得る際に、それらの古典アルゴリズムよりも有利であることが期待されている。
我々は,1次元bppに対して,単一容器で実現可能な解を量子アニーリングサブルーチンを用いてサンプル化するハイブリッド手法を提案している。
この縮小された探索空間から、古典的な最適化サブルーチンは問題の解を見つけることができる。
本稿では,我々のサブルーチンの評価を一歩進めることを目的として,他の古典的手法と比較する。
具体的にはランダムサンプリングとランダムウォークに基づくヒューリスティックをテストする。
18のインスタンスからなるベンチマークを用いて、量子アプローチは古典的アルゴリズムを遅くする停滞挙動を欠いていることを示す。
この結果から,ランダムウォークと共同で量子戦略を用い,より少ないイテレーションで実現可能な解の完全なサンプルを得ることができると結論づけた。
この研究は、少ない量子資源を使うことによる利点に関する直感を改善し、より効率的な古典的戦略の結果を改善する。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳（メタデータ） (2024-11-07T17:05:31Z) - 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) - Iterative Quantum Algorithms for Maximum Independent Set: A Tale of
Low-Depth Quantum Algorithms [0.0]
我々は、反復最大量子アルゴリズム(Iterative Maximum Quantum Algorithms)と呼ばれる、量子最適化のための新しいハイブリッドアプローチのクラスについて研究する。
深度$p=1$のQAOAの場合、このアルゴリズムはMISの古典的欲求アルゴリズムと全く同じ操作と選択を行う。
論文 参考訳（メタデータ） (2023-09-22T18:00:03Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳（メタデータ） (2023-06-15T15:28:12Z) - A quantum advantage over classical for local max cut [48.02822142773719]
量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。
結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
論文 参考訳（メタデータ） (2023-04-17T16:42:05Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Adapting Quantum Approximation Optimization Algorithm (QAOA) for Unit
Commitment [2.8060379263058794]
ユニットコミットと呼ばれる電力系統最適化問題に対して,ハイブリッド量子古典アルゴリズムを定式化し,適用する。
提案アルゴリズムは、量子近似最適化アルゴリズム(QAOA)を古典最小値で拡張し、混合二元最適化をサポートする。
提案手法は,400個の発電ユニット未満のシミュレーション単位コミットに対して,古典的解法が有効であることを示す。
論文 参考訳（メタデータ） (2021-10-25T03:37:34Z) - Quantum Optimization Heuristics with an Application to Knapsack Problems [5.866941279460248]
本稿では,量子近似最適化アルゴリズム(QAOA)を制約付き最適化問題に適合させる2つの手法を提案する。
最初のテクニックでは、初期の量子状態と混合操作を定義し、量子最適化アルゴリズムを調整して、この初期欲求解に関する可能な解を探索する方法が述べられている。
第2の手法は、グリーディ溶液の周りの局所的なミニマを避けるために、量子探索に使用される。
論文 参考訳（メタデータ） (2021-08-19T17:22:44Z) - An optimal quantum sampling regression algorithm for variational
eigensolving in the low qubit number regime [0.0]
量子サンプリング回帰(QSR)は、代替の量子古典的アルゴリズムである。
低量子ビット数構造における時間的複雑さに基づいて,その利用事例を分析した。
ベンチマーク問題に対するアルゴリズムの有効性を示す。
論文 参考訳（メタデータ） (2020-12-04T00:01:15Z) - Tabu-driven Quantum Neighborhood Samplers [2.9934511331003555]
組合せ最適化は、量子コンピューティングを対象とする重要なアプリケーションである。
短期的なデバイスで利点を享受する一つの選択肢は、それらを古典と組み合わせて使うことである。
このようなハイブリッド環境において,QAOAはアルゴリズム探索のための柔軟なツールであることを示す。
論文 参考訳（メタデータ） (2020-11-18T19:30:27Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。