論文の概要: Analyzing Prospects for Quantum Advantage in Topological Data Analysis
- arxiv url: http://arxiv.org/abs/2209.13581v3
- Date: Wed, 27 Sep 2023 21:19:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 23:04:55.193433
- Title: Analyzing Prospects for Quantum Advantage in Topological Data Analysis
- Title（参考訳）: トポロジカルデータ分析における量子アドバンテージの分析
- Authors: Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso,
Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko and
Ryan Babbush
- Abstract要約: 我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
- 参考スコア（独自算出の注目度）: 35.423446067065576
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Lloyd et al. were first to demonstrate the promise of quantum algorithms for
computing Betti numbers, a way to characterize topological features of data
sets. Here, we propose, analyze, and optimize an improved quantum algorithm for
topological data analysis (TDA) with reduced scaling, including a method for
preparing Dicke states based on inequality testing, a more efficient amplitude
estimation algorithm using Kaiser windows, and an optimal implementation of
eigenvalue projectors based on Chebyshev polynomials. We compile our approach
to a fault-tolerant gate set and estimate constant factors in the Toffoli
complexity. Our analysis reveals that super-quadratic quantum speedups are only
possible for this problem when targeting a multiplicative error approximation
and the Betti number grows asymptotically. Further, we propose a dequantization
of the quantum TDA algorithm that shows that having exponentially large
dimension and Betti number are necessary, but insufficient conditions, for
super-polynomial advantage. We then introduce and analyze specific problem
examples which have parameters in the regime where super-polynomial advantages
may be achieved, and argue that quantum circuits with tens of billions of
Toffoli gates can solve seemingly classically intractable instances.
- Abstract（参考訳）: ロイドらは、データセットの位相的特徴を特徴づける方法であるベッチ数を計算するための量子アルゴリズムの可能性を最初に示した。
本稿では,不等式テストに基づくディッケ状態の生成法,カイザー窓を用いたより効率的な振幅推定法,チェビシェフ多項式に基づく固有値プロジェクタの最適実装を含む,縮小スケーリングによる位相データ解析(tda)のための改良量子アルゴリズムを提案し,解析し,最適化する。
我々はフォールトトレラントゲート集合へのアプローチをコンパイルし、トッフォリ複雑性の定数因子を推定する。
解析の結果,乗法誤差近似とベッチ数が漸近的に増大する場合に,超二次量子スピードアップはこの問題に対してのみ可能であることがわかった。
さらに, 指数的に大きな次元とベッチ数を持つことは必要だが, 超ポリノミカル・アドバンテージのためには不十分であることを示す量子TDAアルゴリズムの定式化を提案する。
次に,超多項的優位性が達成されるようなシステムにおいてパラメータを持つ特定の問題例を紹介し解析し,数十億の toffoli ゲートを持つ量子回路は古典的に難解なインスタンスを解くことができると主張する。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
行列乗法重み付けアルゴリズムの量子化'''は、古典的アルゴリズムよりも2次的に高速なSDPの近似解が得られることを示す。
この量子アルゴリズムを改良し、ギブス状態サンプリング器を熱純量子(TPQ)状態に置き換えることで、同様のスピードアップが得られることを示す。
論文 参考訳（メタデータ） (2023-10-11T18:00:53Z) - Robust Dequantization of the Quantum Singular value Transformation and
Quantum Machine Learning Algorithms [0.0]
この弱い仮定の下では、ランダム化線形代数の技法がどれだけ多く適用できるかを示す。
また、これらの結果を用いて、多くの量子機械学習アルゴリズムの頑健な復号化を行う。
論文 参考訳（メタデータ） (2023-04-11T02:09:13Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Towards quantum advantage via topological data analysis [0.0]
ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。
ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-05-06T06:31:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。