Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914134678831104 |
|---|---|
| author | Akhalwaya, Ismail Yunus Bhayat, Ahmed Connolly, Adam Herbert, Steven Horesh, Lior Sorci, Julien Ubaru, Shashanka |
| author_facet | Akhalwaya, Ismail Yunus Bhayat, Ahmed Connolly, Adam Herbert, Steven Horesh, Lior Sorci, Julien Ubaru, Shashanka |
| contents | Several quantum and classical Monte Carlo algorithms for Betti Number Estimation (BNE) on clique complexes have recently been proposed, though it is unclear how their performances compare. We review these algorithms, emphasising their common Monte Carlo structure within a new modular framework. We derive upper bounds for the number of samples needed to reach a given level of precision, and use them to compare these algorithms. By recombining the different modules, we create a new quantum algorithm with an exponentially-improved dependence in the sample complexity. We run classical simulations to verify convergence within the theoretical bounds and observe the predicted exponential separation, even though empirical convergence occurs substantially earlier than the conservative theoretical bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16934 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes Akhalwaya, Ismail Yunus Bhayat, Ahmed Connolly, Adam Herbert, Steven Horesh, Lior Sorci, Julien Ubaru, Shashanka Quantum Physics Several quantum and classical Monte Carlo algorithms for Betti Number Estimation (BNE) on clique complexes have recently been proposed, though it is unclear how their performances compare. We review these algorithms, emphasising their common Monte Carlo structure within a new modular framework. We derive upper bounds for the number of samples needed to reach a given level of precision, and use them to compare these algorithms. By recombining the different modules, we create a new quantum algorithm with an exponentially-improved dependence in the sample complexity. We run classical simulations to verify convergence within the theoretical bounds and observe the predicted exponential separation, even though empirical convergence occurs substantially earlier than the conservative theoretical bounds. |
| title | Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.16934 |