Uniformity testing when you have the source code
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_ | 1866917830540132352 |
|---|---|
| author | Canonne, Clément L. Kothari, Robin O'Donnell, Ryan |
| author_facet | Canonne, Clément L. Kothari, Robin O'Donnell, Ryan |
| contents | We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the distribution. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on $[d]$ or $ε$-far from uniform in total variation distance. More generally, we consider identity testing, which is the task of deciding if the output distribution equals a known hypothesis distribution, or is $ε$-far from it. For both problems, the previous best known upper bound was $O(\min\{d^{1/3}/ε^{2},d^{1/2}/ε\})$. Here we improve the upper bound to $O(\min\{d^{1/3}/ε^{4/3}, d^{1/2}/ε\})$, which we conjecture is optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04972 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Uniformity testing when you have the source code Canonne, Clément L. Kothari, Robin O'Donnell, Ryan Quantum Physics Computational Complexity Data Structures and Algorithms We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the distribution. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on $[d]$ or $ε$-far from uniform in total variation distance. More generally, we consider identity testing, which is the task of deciding if the output distribution equals a known hypothesis distribution, or is $ε$-far from it. For both problems, the previous best known upper bound was $O(\min\{d^{1/3}/ε^{2},d^{1/2}/ε\})$. Here we improve the upper bound to $O(\min\{d^{1/3}/ε^{4/3}, d^{1/2}/ε\})$, which we conjecture is optimal. |
| title | Uniformity testing when you have the source code |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.04972 |