Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917704857812992 |
|---|---|
| author | Luo, Jingquan Wang, Qisheng Li, Lvzhou |
| author_facet | Luo, Jingquan Wang, Qisheng Li, Lvzhou |
| contents | We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions.
Closeness testing is the problem of distinguishing whether two $n$-dimensional distributions are identical or at least $\varepsilon$-far in $\ell^1$- or $\ell^2$-distance. We show that the quantum query complexities for $\ell^1$- and $\ell^2$-closeness testing are $O(\sqrt{n}/\varepsilon)$ and $O(1/\varepsilon)$, respectively, both of which achieve optimal dependence on $\varepsilon$, improving the prior best results of Gilyén and Li (2020).
$k$-wise uniformity testing is the problem of distinguishing whether a distribution over $\{0, 1\}^n$ is uniform when restricted to any $k$ coordinates or $\varepsilon$-far from any such distributions. We propose the first quantum algorithm for this problem with query complexity $O(\sqrt{n^k}/\varepsilon)$, achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexity $O(n^k/\varepsilon^2)$ by O'Donnell and Zhao (2018). Moreover, when $k = 2$ our quantum algorithm outperforms any classical one because of the classical lower bound $Ω(n/\varepsilon^2)$.
All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_12916 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions Luo, Jingquan Wang, Qisheng Li, Lvzhou Quantum Physics We explore potential quantum speedups for the fundamental problem of testing the properties of closeness and $k$-wise uniformity of probability distributions. Closeness testing is the problem of distinguishing whether two $n$-dimensional distributions are identical or at least $\varepsilon$-far in $\ell^1$- or $\ell^2$-distance. We show that the quantum query complexities for $\ell^1$- and $\ell^2$-closeness testing are $O(\sqrt{n}/\varepsilon)$ and $O(1/\varepsilon)$, respectively, both of which achieve optimal dependence on $\varepsilon$, improving the prior best results of Gilyén and Li (2020). $k$-wise uniformity testing is the problem of distinguishing whether a distribution over $\{0, 1\}^n$ is uniform when restricted to any $k$ coordinates or $\varepsilon$-far from any such distributions. We propose the first quantum algorithm for this problem with query complexity $O(\sqrt{n^k}/\varepsilon)$, achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexity $O(n^k/\varepsilon^2)$ by O'Donnell and Zhao (2018). Moreover, when $k = 2$ our quantum algorithm outperforms any classical one because of the classical lower bound $Ω(n/\varepsilon^2)$. All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation. |
| title | Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2304.12916 |