Succinct Quantum Testers for Closeness and k-Wise Uniformity of Probability Distributions

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 ε-far in ℓ 1 - or ℓ 2 -distance. We show that the quantum query complexities for ℓ 1 - and ℓ 2 -closeness testing are O (√ n /ε) and O (1/ε), respectively, both of which achieve optimal dependence on ε, improving the prior best results of Gilyén and Li (2019). • 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 ε-far from any such distribution. We propose the first quantum algorithm for this problem with query complexity O (√ n k /ε), achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexity O ( n k /ε 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 /ε 2 ). All our quantum algorithms are fairly simple and time-efficient, using only basic quantum subroutines such as amplitude estimation.