| Autor: |
Simon Apers, Sander Gribling, Sayantan Sen, Dániel Szabó |
| Jazyk: |
angličtina |
| Rok vydání: |
2023 |
| Předmět: |
|
| Zdroj: |
Quantum, Vol 7, p 1202 (2023) |
| Druh dokumentu: |
article |
| ISSN: |
2521-327X |
| DOI: |
10.22331/q-2023-12-06-1202 |
| Popis: |
We describe a simple algorithm for estimating the $k$-th normalized Betti number of a simplicial complex over $n$ elements using the path integral Monte Carlo method. For a general simplicial complex, the running time of our algorithm is $n^{O\left(\frac{1}{\sqrt{\gamma}}\log\frac{1}{\varepsilon}\right)}$ with $\gamma$ measuring the spectral gap of the combinatorial Laplacian and $\varepsilon \in (0,1)$ the additive precision. In the case of a clique complex, the running time of our algorithm improves to $\left(n/\lambda_{\max}\right)^{O\left(\frac{1}{\sqrt{\gamma}}\log\frac{1}{\varepsilon}\right)}$ with $\lambda_{\max} \geq k$, where $\lambda_{\max}$ is the maximum eigenvalue of the combinatorial Laplacian. Our algorithm provides a classical benchmark for a line of quantum algorithms for estimating Betti numbers. On clique complexes it matches their running time when, for example, $\gamma \in \Omega(1)$ and $k \in \Omega(n)$. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
