論文の概要: 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に等しく適用可能であることを確信します。
関連論文リスト
- Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [2.4968861883180447]
対角ハミルトニアンの基底状態解を見つけることは、金融、物理学、計算機科学など多くの分野に関心を持つ理論的および実践的な問題の両方に関係している。
ここでは、新しいブロック符号化方式を用いて、これらの問題の基底状態を取得し、この手法をMaxCutに例証として応用する。
論文 参考訳（メタデータ） (2024-11-16T08:17:36Z) - Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
変分アルゴリズム (VQA) は, NISQシステムの実用化に向けた最有力候補の1つである。
本稿では,VQAの現状と最近の発展を考察し,近似最適化への適用性を強調した。
10ノードと20ノードのグラフ上でMaxCut問題を解くために,深さの異なるQAOA回路を実装した。
論文 参考訳（メタデータ） (2024-07-08T22:02:39Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - 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) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳（メタデータ） (2021-12-21T12:41:31Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。