論文の概要: To quantum or not to quantum: towards algorithm selection in near-term
quantum optimization
- arxiv url: http://arxiv.org/abs/2001.08271v2
- Date: Wed, 14 Oct 2020 10:54:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-06 06:59:29.217697
- Title: To quantum or not to quantum: towards algorithm selection in near-term
quantum optimization
- Title(参考訳): 量子化・量子化へ:短期的量子最適化におけるアルゴリズム選択に向けて
- Authors: Charles Moussa, Henri Calandra, Vedran Dunjko
- Abstract要約: 本稿では,QAOAが従来のアルゴリズムよりも有利になる確率の高い問題事例を検出する問題について検討する。
クロスバリデーションの精度は96%以上で、実用的な優位性が得られる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Quantum Approximate Optimization Algorithm (QAOA) constitutes one of the
often mentioned candidates expected to yield a quantum boost in the era of
near-term quantum computing. In practice, quantum optimization will have to
compete with cheaper classical heuristic methods, which have the advantage of
decades of empirical domain-specific enhancements. Consequently, to achieve
optimal performance we will face the issue of algorithm selection, well-studied
in practical computing. Here we introduce this problem to the quantum
optimization domain.
Specifically, we study the problem of detecting those problem instances of
where QAOA is most likely to yield an advantage over a conventional algorithm.
As our case study, we compare QAOA against the well-understood approximation
algorithm of Goemans and Williamson (GW) on the Max-Cut problem. As exactly
predicting the performance of algorithms can be intractable, we utilize machine
learning to identify when to resort to the quantum algorithm. We achieve
cross-validated accuracy well over 96\%, which would yield a substantial
practical advantage. In the process, we highlight a number of features of
instances rendering them better suited for QAOA. While we work with simulated
idealised algorithms, the flexibility of ML methods we employed provides
confidence that our methods will be equally applicable to broader classes of
classical heuristics, and to QAOA running on real-world noisy devices.
- Abstract(参考訳): 量子近似最適化アルゴリズム (Quantum Approximate Optimization Algorithm, QAOA) は、短期量子コンピューティングの時代において量子アップを期待される候補の1つである。
実際、量子最適化は、数十年に及ぶ経験的ドメイン固有の拡張の利点を持つ安価な古典的ヒューリスティック手法と競合する必要がある。
したがって、最適性能を達成するために、実用的な計算でよく研究されているアルゴリズム選択の問題に直面する。
ここではこの問題を量子最適化領域に導入する。
具体的には、QAOAが従来のアルゴリズムよりも有利になる確率の高い問題を検知する問題について検討する。
ケーススタディとして,最大カット問題に対するgoemans と williamson (gw) のよく知られた近似アルゴリズムとqaoaを比較した。
アルゴリズムの性能を正確に予測することは難解であり、機械学習を使っていつ量子アルゴリズムに頼るべきかを特定する。
96 %以上の精度でクロスバリデーションを達成でき、実用的な優位性が得られる。
このプロセスでは、QAOAに適したインスタンスをレンダリングする多くの機能を強調します。
シミュレーションされた理想化されたアルゴリズムで作業する一方で、私達が採用したMLメソッドの柔軟性は、我々のメソッドが古典的ヒューリスティックスのより広範なクラス、および実世界のノイズの多いデバイスで動作するQAOAに等しく適用可能であることを確信します。
関連論文リスト
- 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) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳(メタデータ) (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Stochastic optimization algorithms for quantum applications [0.0]
本稿では、一階法、二階法、量子自然勾配最適化法の使用法を概観し、複素数体で定義される新しいアルゴリズムを提案する。
全ての手法の性能は、変分量子固有解法、量子状態の量子制御、および量子状態推定に応用して評価される。
論文 参考訳(メタデータ) (2022-03-11T16:17:05Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳(メタデータ) (2021-12-21T12:41:31Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳(メタデータ) (2021-05-14T11:31:14Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳(メタデータ) (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。