論文の概要: Quantum Algorithms for Community Detection and their Empirical Run-times
- arxiv url: http://arxiv.org/abs/2203.06208v1
- Date: Fri, 11 Mar 2022 19:02:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-22 09:13:07.051126
- Title: Quantum Algorithms for Community Detection and their Empirical Run-times
- Title（参考訳）: コミュニティ検出のための量子アルゴリズムとその経験的実行時間
- Authors: Chris Cade, Marten Folkertsma, Ido Niesen, Jordi Weggemans
- Abstract要約: 我々は、控えめなスピードアップを伴う単純な量子アルゴリズムが、実際は最高の性能を発揮するものであることを示している。
量子サブルーチンの成功を増幅する必要性から生じるオーバーヘッドのようなオーバーヘッドは、理論的に最悪のケース分析や予測ケース分析によって示唆されたであろうスピードアップを無効化できる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We apply our recent work on empirical estimates of quantum speedups to the
practical task of community detection in complex networks. We design several
quantum variants of a popular classical algorithm -- the Louvain algorithm for
community detection -- and first study their complexities in the usual way,
before analysing their complexities empirically across a variety of artificial
and real inputs. We find that this analysis yields insights not available to us
via the asymptotic analysis, further emphasising the utility in such an
empirical approach. In particular, we observe that a complicated quantum
algorithm with a large asymptotic speedup might not be the fastest algorithm in
practice, and that a simple quantum algorithm with a modest speedup might in
fact be the one that performs best. Moreover, we repeatedly find that overheads
such as those arising from the need to amplify the success probabilities of
quantum sub-routines such as Grover search can nullify any speedup that might
have been suggested by a theoretical worst- or expected-case analysis.
- Abstract（参考訳）: 量子スピードアップの実証的推定に関する最近の研究を,複雑なネットワークにおけるコミュニティ検出の実践的タスクに適用する。
一般的な古典的アルゴリズム – コミュニティ検出のためのルーバンアルゴリズム – の量子変種をいくつか設計し、その複雑さを通常の方法で研究し、その後、さまざまな人工的および実入力を経験的に分析します。
この分析は漸近分析では得られない洞察をもたらし、このような経験的アプローチでの有用性をさらに強調する。
特に、大きな漸近速度アップを持つ複雑な量子アルゴリズムは、実際には最速のアルゴリズムではないかもしれないし、控えめなスピードアップを持つ単純な量子アルゴリズムは、実際には最もパフォーマンスの高い量子アルゴリズムであるかもしれない。
さらに、グロバー探索のような量子サブルーチンの成功確率を増幅する必要性から生じるオーバーヘッドは、理論的に最悪のケースや予測ケース分析によって示唆されたであろうスピードアップを無効化することができることを繰り返し見出した。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Realistic Runtime Analysis for Quantum Simplex Computation [0.4407851469168588]
重要な最適化問題の現実のインスタンスを解く際に,古典的ランタイム解析のための量子アナログを提案する。
現実的な問題サイズに対する現実的な量子的優位性は、現在の物理的な制限よりもかなり低い量子ゲート演算時間を必要とすることを示します。
論文 参考訳（メタデータ） (2023-11-16T16:11:44Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - 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) - 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) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
古典的なエミュレーションと、すべての定数を含む詳細な複雑性境界を組み合わせたアプローチを考える。
本手法を古典的アルゴリズムの単純量子スピードアップに適用し,よく研究されたMAX-$k$-SAT最適化問題を解く。
これは、2つの重要な量子サブルーチンの期待と最悪のケースの複雑さに厳密な境界(全定数を含む)を必要とする。
論文 参考訳（メタデータ） (2022-03-09T19:00:00Z) - Hybrid Quantum-Classical Search Algorithms [0.0]
古典計算は,探索問題自体が解けない限り,量子計算を補助できないことを示す。
我々はこの結果を、不安定な成功確率を持つアルゴリズムに一般化する。
論文 参考訳（メタデータ） (2022-02-23T11:43:17Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
量子力学シミュレーションのための量子アルゴリズムは、伝統的に時間進化作用素のトロッター近似の実装に基づいている。
変分量子アルゴリズムは欠かせない代替手段となり、現在のハードウェア上での小規模なシミュレーションを可能にしている。
量子ゲートコストが明らかに削減されているにもかかわらず、現在の実装における変分法は量子的優位性をもたらすことはありそうにない。
論文 参考訳（メタデータ） (2021-08-09T18:00:05Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-05-06T06:31:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。