Related papers: Alternative Method for Estimating Betti Numbers

Alternative Method for Estimating Betti Numbers

URL: http://arxiv.org/abs/2403.04686v2
Date: Sun, 21 Apr 2024 15:10:08 GMT
Title: Alternative Method for Estimating Betti Numbers
Authors: Nhat A. Nghiem,
Abstract summary: We provide an alternative method for estimating Betti numbers and normalized Betti numbers of given simplicial complex. Our method can be faster than the best-known classical method for finding Betti numbers. Our method could match the running time of best-known quantum method in the case of dense simplices.
Score: 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.

Related papers

Quantum Bayesian Optimization [64.58749619145908]
We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
arXiv Detail & Related papers (2023-10-09T03:10:42Z)
Quantum Algorithm for Estimating Betti Numbers Using a Cohomology Approach [2.2000560351723504]
Calculating Betti numbers classically is a daunting task due to the massive volume of data. We consider the dual' approach, which is inspired by Hodge theory and de Rham cohomology. Our algorithm can calculate its $r$-th Betti number $beta_r$ up to some multiplicative error.
arXiv Detail & Related papers (2023-09-19T17:44:53Z)
An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum Topological Data Analysis [1.2246649738388387]
We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex. Our algorithm works best when the complex has close to the maximal number of simplices.
arXiv Detail & Related papers (2023-07-13T21:46:45Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z)
A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits [5.478764356647437]
We present an improved quantum algorithm for computing persistent Betti numbers. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
arXiv Detail & Related papers (2022-09-26T17:56:11Z)
Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z)
A hybrid quantum image edge detector for the NISQ era [62.997667081978825]
We propose a hybrid method for quantum edge detection based on the idea of a quantum artificial neuron. Our method can be practically implemented on quantum computers, especially on those of the current noisy intermediate-scale quantum era.
arXiv Detail & Related papers (2022-03-22T22:02:09Z)
Quantum algorithm for persistent Betti numbers and topological data analysis [0.0]
This paper shows the first quantum algorithm that can estimate the persistent Betti numbers of arbitrary dimensions. Our algorithm is efficient for simplicial complexes such as the Vietoris-Rips complex and demonstrates exponential speedup over the known classical algorithms.
arXiv Detail & Related papers (2021-10-31T09:02:01Z)
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
arXiv Detail & Related papers (2020-11-09T01:13:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.