論文の概要: Quantum Topological Data Analysis with Linear Depth and Exponential Speedup

• arxiv url: http://arxiv.org/abs/2108.02811v1
• Date: Thu, 5 Aug 2021 18:56:17 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-09 14:22:13.510931
• Title: Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• Title（参考訳）: 線形深さと指数速度を用いた量子トポロジカルデータ解析
• Authors: Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S. Squillante, Kenneth L. Clarkson, Lior Horesh
• Abstract要約: 我々はQTDAアルゴリズムを完全にオーバーホールし、$O(n4/(epsilon2 delta))の指数的高速化深度を改良した。 理論的誤差解析とベッチ数推定のための回路・計算時間・深度複雑度について述べる。
• 参考スコア（独自算出の注目度）: 9.820545418277305
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing offers the potential of exponential speedups for certain classical computations. Over the last decade, many quantum machine learning (QML) algorithms have been proposed as candidates for such exponential improvements. However, two issues unravel the hope of exponential speedup for some of these QML algorithms: the data-loading problem and, more recently, the stunning dequantization results of Tang et al. A third issue, namely the fault-tolerance requirements of most QML algorithms, has further hindered their practical realization. The quantum topological data analysis (QTDA) algorithm of Lloyd, Garnerone and Zanardi was one of the first QML algorithms that convincingly offered an expected exponential speedup. From the outset, it did not suffer from the data-loading problem. A recent result has also shown that the generalized problem solved by this algorithm is likely classically intractable, and would therefore be immune to any dequantization efforts. However, the QTDA algorithm of Lloyd et~al. has a time complexity of $O(n^4/(\epsilon^2 \delta))$ (where $n$ is the number of data points, $\epsilon$ is the error tolerance, and $\delta$ is the smallest nonzero eigenvalue of the restricted Laplacian) and requires fault-tolerant quantum computing, which has not yet been achieved. In this paper, we completely overhaul the QTDA algorithm to achieve an improved exponential speedup and depth complexity of $O(n\log(1/(\delta\epsilon)))$. Our approach includes three key innovations: (a) an efficient realization of the combinatorial Laplacian as a sum of Pauli operators; (b) a quantum rejection sampling approach to restrict the superposition to the simplices in the complex; and (c) a stochastic rank estimation method to estimate the Betti numbers. We present a theoretical error analysis, and the circuit and computational time and depth complexities for Betti number estimation.
• Abstract（参考訳）: 量子コンピューティングは、ある種の古典的な計算に対して指数的スピードアップの可能性を提供する。 過去10年間で、このような指数関数的改善の候補として多くの量子機械学習(QML)アルゴリズムが提案されている。 しかし、この2つの問題は、これらのqmlアルゴリズムのいくつかに指数関数的なスピードアップの希望をもたらす:データローディング問題、そして最近では、tangらによる驚くべき非量子化結果である。 第3の課題、すなわちほとんどのQMLアルゴリズムのフォールトトレランス要件は、その実践的実現をさらに妨げている。 Lloyd, Garnerone, Zanardiの量子トポロジカルデータ解析(QTDA)アルゴリズムは、予想される指数的スピードアップを提供する最初のQMLアルゴリズムの1つである。 当初から、データローディングの問題に悩まされていなかった。 最近の結果は、このアルゴリズムによって解決された一般化された問題は、古典的に難解であり、従っていかなる解量化努力にも無関係であることも示している。 しかし、lloyd et~alのqtdaアルゴリズム。 時間複雑性は$O(n^4/(\epsilon^2 \delta))$($n$はデータポイントの数、$\epsilon$はエラートレランス、$\delta$は制限されたラプラシアンの最小の非ゼロ固有値であり、まだ達成されていないフォールトトレラント量子コンピューティングを必要とする。 本稿では,QTDAアルゴリズムを改良した指数的高速化と深さ複雑性を$O(n\log(1/(\delta\epsilon))$で実現する。 このアプローチには、3つの重要な革新がある: (a) パウリ作用素の和としての組合せラプラシアンの効率的な実現、(b)複素体の単純さに重畳を制限する量子拒絶サンプリングアプローチ、(c)ベッチ数を推定する確率的ランク推定方法。 理論的誤差解析とベッチ数推定のための回路・計算時間・深度複雑度について述べる。

関連論文リスト

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
  古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。 我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。 我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
  論文  参考訳（メタデータ） (2023-12-21T18:57:54Z)
• Taming Quantum Time Complexity [50.10645865330582]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  Harrow-Hassidim-Lloyd (HHL) の量子力学的実装から有用な情報が抽出可能であることを示す。 しかし,本論文では,HHLの量子力学的実装から有用な情報を抽出し,古典的側面における解を見つける際の複雑性を低減することを目的としている。
  論文  参考訳（メタデータ） (2022-10-23T11:58:05Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Quantum Sparse Coding [5.130440339897477]
  我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。 量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。 我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
  論文  参考訳（メタデータ） (2022-09-08T13:00:30Z)
• Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
  Z_N$のディヘドラルコセット問題(DCP)は量子コンピューティングやポスト量子暗号において広く研究されている。 Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られている。 本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-29T05:30:54Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。