論文の概要: Alternative Method for Estimating Betti Numbers
- arxiv url: http://arxiv.org/abs/2403.04686v2
- Date: Sun, 21 Apr 2024 15:10:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-23 23:24:19.074597
- Title: Alternative Method for Estimating Betti Numbers
- Title（参考訳）: ベティ数推定法
- Authors: Nhat A. Nghiem,
- Abstract要約: 与えられた単純複素数のベッチ数と正規化ベッチ数を推定する別の方法を提案する。
我々の手法はベッチ数を見つけるのによく知られた古典的手法よりも高速である。
本手法は,高密度な単純化の場合,最もよく知られた量子法の実行時間と一致する可能性がある。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Topological data analysis (TDA) is a fast-growing field that utilizes advanced tools from topology to analyze large-scale data. A central problem in topological data analysis is estimating the so-called Betti numbers of the underlying simplicial complex. While the difficulty of this problem has been established as NP-hard, previous works have showcased appealing quantum speedup. In this article, we provide an alternative method for estimating Betti numbers and normalized Betti numbers of given simplicial complex, based on some recent advances in quantum algorithm, specifically, quantum singular value transformation. Our method can be faster than the best-known classical method for finding Betti numbers, and interestingly, it can also find the Betti numbers of the complement graph to our original one. Comparing to the best known quantum algorithm, our method generally requires lower depth circuit, in trade-off for longer running time. Regarding normalized Betti numbers, our method could match the running time of best-known quantum method in the case of dense simplices.
- Abstract（参考訳）: トポロジカルデータ分析(TDA)は、トポロジから高度なツールを用いて大規模データを分析する、急速に成長する分野である。
トポロジカルデータ解析における中心的な問題は、下層の単純複素数のいわゆるベッチ数の推定である。
この問題の難しさはNPハードとして確立されているが、以前の研究では量子スピードアップが魅力的であった。
本稿では、量子アルゴリズム、特に量子特異値変換の最近の進歩に基づき、与えられた単体錯体のベッチ数と正規化ベッチ数を推定する代替手法を提案する。
我々の手法は、ベッチ数を見つける最もよく知られた古典的方法よりも高速であり、興味深いことに、補グラフのベッチ数を見つけることもできる。
最もよく知られた量子アルゴリズムと比較して、我々の手法は一般的により低い深さの回路を必要とする。
正規化されたベティ数については,高密度な単純化の場合,最もよく知られた量子法の実行時間と一致する可能性がある。
関連論文リスト
- Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。
O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。
線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文 参考訳（メタデータ） (2023-10-09T03:10:42Z) - Quantum Algorithm for Estimating Betti Numbers Using a Cohomology
Approach [2.2000560351723504]
ベティの数値を古典的に計算することは膨大な量のデータのために大変な作業である。
ホッジ理論とド・ラムコホモロジーにインスパイアされた「双対」アプローチを考える。
我々のアルゴリズムは、その$r$-th Betti number $beta_r$を乗算誤差まで計算できる。
論文 参考訳（メタデータ） (2023-09-19T17:44:53Z) - An Incremental Span-Program-Based Algorithm and the Fine Print of
Quantum Topological Data Analysis [1.2246649738388387]
単純複素数のベッチ数を計算するための新しい量子アルゴリズムを提案する。
我々のアルゴリズムは、複素数が最大数の単純数に近い場合に最もよく機能する。
論文 参考訳（メタデータ） (2023-07-13T21:46:45Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - A streamlined quantum algorithm for topological data analysis with
exponentially fewer qubits [5.478764356647437]
永続ベッチ数を計算するための改良された量子アルゴリズムを提案する。
量子アルゴリズムが実用的なタスクの指数的高速化を達成できるかどうかを論じる。
論文 参考訳（メタデータ） (2022-09-26T17:56:11Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - A hybrid quantum image edge detector for the NISQ era [62.997667081978825]
本稿では,量子人工ニューロンのアイデアに基づく量子エッジ検出のハイブリッド手法を提案する。
提案手法は, 量子コンピュータ, 特に現在ノイズの多い中間量子時代において, 実際に実装することができる。
論文 参考訳（メタデータ） (2022-03-22T22:02:09Z) - Quantum algorithm for persistent Betti numbers and topological data
analysis [0.0]
本稿では,任意の次元のベッチ数を推定できる最初の量子アルゴリズムを示す。
我々のアルゴリズムは、ビエトリス・リプス複素数のような単純な複素数に対して効率的であり、既知の古典的アルゴリズムよりも指数的なスピードアップを示す。
論文 参考訳（メタデータ） (2021-10-31T09:02:01Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。