論文の概要: Comparing the Digital Annealer with Classical Evolutionary Algorithm
- arxiv url: http://arxiv.org/abs/2205.13586v1
- Date: Thu, 26 May 2022 19:04:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-30 14:40:24.612918
- Title: Comparing the Digital Annealer with Classical Evolutionary Algorithm
- Title（参考訳）: デジタルアニールと古典的進化アルゴリズムの比較
- Authors: Mayowa Ayodele
- Abstract要約: 特殊なハードウェアを使用するソルバの例として、IBMのQuantum System OneとD-waveのQuantum Annealer (QA)、富士通のDigital Annealer (DA)がある。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In more recent years, there has been increasing research interest in
exploiting the use of application specific hardware for solving optimisation
problems. Examples of solvers that use specialised hardware are IBM's Quantum
System One and D-wave's Quantum Annealer (QA) and Fujitsu's Digital Annealer
(DA). These solvers have been developed to optimise problems faster than
traditional meta-heuristics implemented on general purpose machines. Previous
research has shown that these solvers (can optimise many problems much quicker
than exact solvers such as GUROBI and CPLEX. Such conclusions have not been
made when comparing hardware solvers with classical evolutionary algorithms.
Making a fair comparison between traditional evolutionary algorithms, such as
Genetic Algorithm (GA), and the DA (or other similar solvers) is challenging
because the later benefits from the use of application specific hardware while
evolutionary algorithms are often implemented on generation purpose machines.
Moreover, quantum or quantum-inspired solvers are limited to solving problems
in a specific format. A common formulation used is Quadratic Unconstrained
Binary Optimisation (QUBO). Many optimisation problems are however constrained
and have natural representations that are non-binary. Converting such problems
to QUBO can lead to more problem difficulty and/or larger search space.
The question addressed in this paper is whether quantum or quantum-inspired
solvers can optimise QUBO transformations of combinatorial optimisation
problems faster than classical evolutionary algorithms applied to the same
problems in their natural representations. We show that the DA often presents
better average objective function values than GA on Travelling Salesman,
Quadratic Assignment and Multi-dimensional Knapsack Problem instances.
- Abstract（参考訳）: 近年,最適化問題の解決にアプリケーション固有のハードウェアを利用する研究への関心が高まっている。
特殊なハードウェアを使用するソルバの例として、IBMのQuantum System OneやD-waveのQuantum Annealer (QA)、富士通のDigital Annealer (DA)がある。
これらの解法は汎用機械に実装された従来のメタヒューリスティックよりも高速に問題を最適化するために開発された。
従来の研究では、これらの解法は(GUROBIやCPLEXのような正確な解法よりもはるかに高速に多くの問題を最適化できる)。
ハードウェアソルバと古典的進化的アルゴリズムを比較する際には、そのような結論は得られていない。
遺伝的アルゴリズム(GA)やDA(または他の類似した解法)のような従来の進化的アルゴリズムを公平に比較することは困難である。
さらに、量子や量子に着想を得た解法は特定の形式での問題解決に限られる。
一般的な定式化は、QUBO ( Quadratic Unconstrained Binary Optimisation) である。
しかし、多くの最適化問題は制約され、非双対的な自然表現を持つ。
このような問題をQUBOに変換することは、より問題の難しさやより広い検索スペースにつながる可能性がある。
本稿では, 量子あるいは量子に触発された解法が, 古典的進化アルゴリズムよりも早く, 組合せ最適化問題のqubo変換を最適化できるかどうかを問う。
DAはトラベリングセールスマン, 擬似アサインメント, 多次元Knapsack問題インスタンスにおいて, GAよりも平均目標関数値がよいことを示す。
関連論文リスト
- Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
本稿では、量子遺伝的アルゴリズム(QGA)を用いて、旅行セールスマン問題(TSP)と呼ばれる新しい問題を解決する方法を実装する。
我々は、この新しいアプローチがいかにうまく機能するかを、古典的遺伝的アルゴリズム(CGA)として知られる従来の手法と比較した。
論文 参考訳（メタデータ） (2024-09-20T08:27:42Z) - 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) - 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) - A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。
しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
論文 参考訳（メタデータ） (2022-10-20T14:54:37Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Training variational quantum algorithms is NP-hard [0.7614628596146599]
古典最適化の問題はNPハードであることが示される。
対数的に多くの量子ビットや自由フェルミオンからなる古典的トラクタブルシステムであっても、最適化はNPハードであることが示される。
論文 参考訳（メタデータ） (2021-01-18T19:00:01Z) - Qualifying quantum approaches for hard industrial optimization problems.
A case study in the field of smart-charging of electric vehicles [0.0]
本稿では,電気自動車のスマートチャージ分野から引き出された2つの産業用NP-Hard問題について事例研究を行う。
量子アルゴリズムは従来の近似アルゴリズムと同じ近似比を示すか、改善する。
次のステップは、より大きなインスタンス上で、実際のデバイス上で、そして対処される問題のより複雑なバージョンに対して、それらを確認することである。
論文 参考訳（メタデータ） (2020-12-29T17:10:31Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z) - Warm-starting quantum optimization [6.832341432995627]
最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。
これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。
同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
論文 参考訳（メタデータ） (2020-09-21T18:00:09Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。