論文の概要: Quantum Algorithm for Estimating Betti Numbers Using a Cohomology
Approach
- arxiv url: http://arxiv.org/abs/2309.10800v1
- Date: Tue, 19 Sep 2023 17:44:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-20 13:12:53.648413
- Title: Quantum Algorithm for Estimating Betti Numbers Using a Cohomology
Approach
- Title（参考訳）: コホモロジーによるベッチ数推定のための量子アルゴリズム
- Authors: Nhat A. Nghiem, Xianfeng David Gu and Tzu-Chieh Wei
- Abstract要約: ベティの数値を古典的に計算することは膨大な量のデータのために大変な作業である。
ホッジ理論とド・ラムコホモロジーにインスパイアされた「双対」アプローチを考える。
我々のアルゴリズムは、その$r$-th Betti number $beta_r$を乗算誤差まで計算できる。
- 参考スコア（独自算出の注目度）: 2.2000560351723504
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Topological data analysis has emerged as a powerful tool for analyzing
large-scale data. High-dimensional data form an abstract simplicial complex,
and by using tools from homology, topological features could be identified.
Given a simplex, an important feature is so-called Betti numbers. Calculating
Betti numbers classically is a daunting task due to the massive volume of data
and its possible high-dimension. While most known quantum algorithms to
estimate Betti numbers rely on homology, here we consider the `dual' approach,
which is inspired by Hodge theory and de Rham cohomology, combined with recent
advanced techniques in quantum algorithms. Our cohomology method offers a
relatively simpler, yet more natural framework that requires exponentially less
qubits, in comparison with the known homology-based quantum algorithms.
Furthermore, our algorithm can calculate its $r$-th Betti number $\beta_r$ up
to some multiplicative error $\delta$ with running time $\mathcal{O}\big(
\log(c_r) c_r^2 / (c_r - \beta_r)^2 \delta^2 \big)$, where $c_r$ is the number
of $r$-simplex. It thus works best when the $r$-th Betti number is considerably
smaller than the number of the $r$-simplex in the given triangulated manifold.
- Abstract（参考訳）: トポロジカルデータ分析は大規模データ分析の強力なツールとして登場した。
高次元データは抽象的単純複体を形成し、ホモロジーのツールを使うことで位相的特徴を識別できる。
単純性が与えられたとき、重要な特徴はいわゆるベッチ数である。
ベッチ数を古典的に計算することは、大量のデータとその高次元の可能性のために厄介な作業である。
ベッチ数を推定する既知の量子アルゴリズムはホモロジーに依存しているが、ここではホッジ理論とド・ラムコホモロジーにインスパイアされた「双対」アプローチと、近年の量子アルゴリズムの先進的手法を組み合わせて考える。
我々のコホモロジー法は、既知のホモロジーに基づく量子アルゴリズムと比較して指数的に少ない量子ビットを必要とする比較的単純だがより自然なフレームワークを提供する。
さらに、我々のアルゴリズムは、その$r$-th Betti number $\beta_r$を、実行時間$\mathcal{O}\big( \log(c_r) c_r^2 / (c_r - \beta_r)^2 \delta^2 \big)$で計算することができる。
したがって、与えられた三角多様体の $r$-simplex の数よりも、$r$-thベッチ数がかなり小さいときに最もよく機能する。
関連論文リスト
- Alternative Method for Estimating Betti Numbers [0.0]
与えられた単純複素数のベッチ数と正規化ベッチ数を推定する別の方法を提案する。
我々の手法はベッチ数を見つけるのによく知られた古典的手法よりも高速である。
本手法は,高密度な単純化の場合,最もよく知られた量子法の実行時間と一致する可能性がある。
論文 参考訳（メタデータ） (2024-03-07T17:32:42Z) - Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文 参考訳（メタデータ） (2023-11-28T21:15:30Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Higher-order topological kernels via quantum computation [68.8204255655161]
トポロジカルデータ分析(TDA)は、複雑なデータから意味のある洞察を抽出する強力なツールとして登場した。
本稿では,ベッチ曲線の次数増加に基づくBettiカーネルの量子的定義法を提案する。
論文 参考訳（メタデータ） (2023-07-14T14:48:52Z) - An Incremental Span-Program-Based Algorithm and the Fine Print of
Quantum Topological Data Analysis [1.2246649738388387]
単純複素数のベッチ数を計算するための新しい量子アルゴリズムを提案する。
我々のアルゴリズムは、複素数が最大数の単純数に近い場合に最もよく機能する。
論文 参考訳（メタデータ） (2023-07-13T21:46:45Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Quantum Approximate Counting for Markov Chains and Application to
Collision Counting [0.0]
我々は,ブラザード,ホイヤー,タップ(ICALP 1998)によって開発された量子近似計数法を一般化し,マルコフ連鎖のマーク状態の数を推定する方法を示す。
これにより、Magniez、Nayak、Roland、Santhaによって確立された強力な"量子ウォークベースサーチ"フレームワークに基づいて、量子検索アルゴリズムから量子近似カウントアルゴリズムを構築することができる。
論文 参考訳（メタデータ） (2022-04-06T03:04:42Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Quantum algorithm for persistent Betti numbers and topological data
analysis [0.0]
本稿では,任意の次元のベッチ数を推定できる最初の量子アルゴリズムを示す。
我々のアルゴリズムは、ビエトリス・リプス複素数のような単純な複素数に対して効率的であり、既知の古典的アルゴリズムよりも指数的なスピードアップを示す。
論文 参考訳（メタデータ） (2021-10-31T09:02:01Z) - Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。
単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:59:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。