Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions

Abstract

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 $\epsilon$-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}/\epsilon )$ and $O(1/\epsilon )$, respectively, both of which achieve optimal dependence on $\epsilon$, 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 $\epsilon$-far from any such distributions. We propose the first quantum algorithm for this problem with query complexity $O(\sqrt{n^k}/\epsilon )$, achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexity $O(n^k/{\epsilon }^2)$ by O'Donnell and Zhao (2018). Moreover, when $k=2$ our quantum algorithm outperforms any classical one because of the classical lower bound $\Omega (n/{\epsilon }^2)$. All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation.

Final version. 26 pages, 2 tables, 3 figures. Improved proofs for Theorem 4 and Theorem 6. Add quantum circuit diagrams. (Corrected abstract display.)

References in corpus (7)

• Simulating Hamiltonian dynamics with a truncated Taylor series
• Improved Bounds on Quantum Learning Algorithms
• New Quantum Algorithms for Computing Quantum Entropies and Distances
• A brief introduction to quantum algorithms
• Fast Quantum Algorithms for Trace Distance Estimation
• Improved Quantum Algorithms for Fidelity Estimation
• A Quantum Algorithm Framework for Discrete Probability Distributions with Applications to Rényi Entropy Estimation

Cited by in corpus (3)

• New Quantum Algorithms for Computing Quantum Entropies and Distances
• Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
• Quantum algorithms for matrix geometric means