論文の概要: Quantifying Grover speed-ups beyond asymptotic analysis
- arxiv url: http://arxiv.org/abs/2203.04975v2
- Date: Thu, 28 Sep 2023 09:30:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 23:15:55.539890
- Title: Quantifying Grover speed-ups beyond asymptotic analysis
- Title（参考訳）: 漸近解析を超えたGroverスピードアップの定量化
- Authors: Chris Cade, Marten Folkertsma, Ido Niesen, Jordi Weggemans
- Abstract要約: 古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。
本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。
これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Run-times of quantum algorithms are often studied via an asymptotic,
worst-case analysis. Whilst useful, such a comparison can often fall short: it
is not uncommon for algorithms with a large worst-case run-time to end up
performing well on instances of practical interest. To remedy this it is
necessary to resort to run-time analyses of a more empirical nature, which for
sufficiently small input sizes can be performed on a quantum device or a
simulation thereof. For larger input sizes, alternative approaches are
required.
In this paper we consider an approach that combines classical emulation with
detailed complexity bounds that include all constants. We simulate quantum
algorithms by running classical versions of the sub-routines, whilst
simultaneously collecting information about what the run-time of the quantum
routine would have been if it were run instead. To do this accurately and
efficiently for very large input sizes, we describe an estimation procedure and
prove that it obtains upper bounds on the true expected complexity of the
quantum algorithms.
We apply our method to some simple quantum speedups of classical heuristic
algorithms for solving the well-studied MAX-$k$-SAT optimization problem. This
requires rigorous bounds (including all constants) on the expected- and
worst-case complexities of two important quantum sub-routines: Grover search
with an unknown number of marked items, and quantum maximum-finding. These
improve upon existing results and might be of broader interest.
Amongst other results, we found that the classical heuristic algorithms we
studied did not offer significant quantum speedups despite the existence of a
theoretical per-step speedup. This suggests that an empirical analysis such as
the one we implement in this paper already yields insights beyond those that
can be seen by an asymptotic analysis alone.
- Abstract（参考訳）: 量子アルゴリズムの実行時間は漸近的かつ最悪のケース分析によってしばしば研究される。
このような比較は役に立つが、しばしば不足することがある。最悪な実行時間を持つアルゴリズムが実践的な関心事の事例でうまく機能するのは珍しいことではない。
これを改善するためには、量子デバイスやシミュレーションで十分に小さな入力サイズを実現できるような、より経験的な性質のランタイム解析に頼る必要がある。
より大きな入力サイズには、代替アプローチが必要である。
本稿では,古典的エミュレーションと,すべての定数を含む詳細な複雑性境界を組み合わせた手法を検討する。
サブルーチンの古典的なバージョンを実行して量子アルゴリズムをシミュレートし、代わりに実行された場合の量子ルーチンの実行時間に関する情報を同時に収集する。
非常に大きな入力サイズに対して,これを高精度かつ効率的に行うために,推定手順を記述し,量子アルゴリズムの真に期待される複雑性の上限を求める。
本手法を古典的ヒューリスティックアルゴリズムの簡単な量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。
これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに関する厳密な境界(全定数を含む)を必要としている。
これらは既存の結果を改善し、より広い関心を持つかもしれない。
その結果,古典的ヒューリスティックアルゴリズムでは,理論的なステップ毎のスピードアップが存在するにも関わらず,大きな量子スピードアップは得られなかった。
このことは、我々が本論文で実施したような経験的分析が、漸近的分析だけで見られるもの以上の洞察を既に得ることを示唆している。
関連論文リスト
- Towards Entropic Constraints on Quantum Speedups [0.0]
いくつかの量子アルゴリズムは「量子スピードアップ(quantum speedups)」を持ち、同じタスクを解くための最もよく知られた古典的アルゴリズムと比較して、時間複雑性を改善している。
エントロピーの観点から、これらのスピードアップに何をもたらすのか理解できますか?
情報理論は、アルゴリズムを実行する量子コンピュータの振る舞いを「量子」がいかに根本的に測定するかを測定するために、私たちが選択できる様々な指標を与えてくれる。
論文 参考訳（メタデータ） (2024-11-05T19:00:04Z) - 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) - Realistic Runtime Analysis for Quantum Simplex Computation [0.4407851469168588]
重要な最適化問題の現実のインスタンスを解く際に,古典的ランタイム解析のための量子アナログを提案する。
現実的な問題サイズに対する現実的な量子的優位性は、現在の物理的な制限よりもかなり低い量子ゲート演算時間を必要とすることを示します。
論文 参考訳（メタデータ） (2023-11-16T16:11:44Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - A streamlined quantum algorithm for topological data analysis with
exponentially fewer qubits [5.478764356647437]
永続ベッチ数を計算するための改良された量子アルゴリズムを提案する。
量子アルゴリズムが実用的なタスクの指数的高速化を達成できるかどうかを論じる。
論文 参考訳（メタデータ） (2022-09-26T17:56:11Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Quantum Algorithms for Community Detection and their Empirical Run-times [0.0]
我々は、控えめなスピードアップを伴う単純な量子アルゴリズムが、実際は最高の性能を発揮するものであることを示している。
量子サブルーチンの成功を増幅する必要性から生じるオーバーヘッドのようなオーバーヘッドは、理論的に最悪のケース分析や予測ケース分析によって示唆されたであろうスピードアップを無効化できる。
論文 参考訳（メタデータ） (2022-03-11T19:02:36Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-05-06T06:31:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。