論文の概要: 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)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• Fast and Practical Quantum-Inspired Classical Algorithms for Solving Linear Systems [11.929584800629673]
  線形系を解くための高速で実用的な量子インスパイアされた古典的アルゴリズムを提案する。 我々の主な貢献は、線形系を解くために量子に着想を得た古典的アルゴリズムへの重球運動量法の適用である。
  論文  参考訳（メタデータ） (2023-07-13T08:46:19Z)
• 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)
• A (simple) classical algorithm for estimating Betti numbers [1.8749305679160366]
  経路積分モンテカルロ法を用いて、$k$-th正規化ベッチ数を$n$要素上の単純複素数として推定する簡単なアルゴリズムを記述する。 一般の単純複素数に対して、我々のアルゴリズムの実行時間は$nOleft(frac1sqrtgammalogfrac1varepsilonright)$で、加法精度は (0,$1) のラプラシアンとヴァレプシロンのスペクトルギャップを測定する$gamma$である。
  論文  参考訳（メタデータ） (2022-11-17T16:10:47Z)
• 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)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  カーネル群に基づく暗黙の空間性誘導機構について述べる。 アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
  論文  参考訳（メタデータ） (2021-10-12T09:36:41Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-01T14:10:38Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。 最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
  論文  参考訳（メタデータ） (2021-04-29T14:50:03Z)
• Faster quantum-inspired algorithms for solving linear systems [0.05076419064097732]
  そこで本研究では,データ構造を$x$で出力する古典的アルゴリズムにより,エントリへのサンプリングとクエリが可能であることを示す。 この出力は、量子線型解法の出力の古典的なアナログと見なすことができる。
  論文  参考訳（メタデータ） (2021-03-18T15:12:44Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)

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

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