We explore potential quantum speedups for the fundamental problem of testing the properties of closeness andk-wise uniformity of probability distributions. •Closeness testingis the problem of distinguishing whether twon-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 areO(√n/ε) andO(1/ε), respectively, both of which achieve optimal dependence on ε, improving the prior best results of Gilyén and Li (2019). •k-wise uniformity testingis the problem of distinguishing whether a distribution over {0, 1}nis uniform when restricted to anykcoordinates or ε-far from any such distribution. We propose the first quantum algorithm for this problem with query complexityO(√nk/ε), achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexityO(nk/ε2) by O’Donnell and Zhao (2018). Moreover, whenk= 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.
We explore potential quantum speedups for the fundamental problem of testing the properties of closeness andk-wise uniformity of probability distributions. •Closeness testingis the problem of distinguishing whether twon-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 areO(√n/ε) andO(1/ε), respectively, both of which achieve optimal dependence on ε, improving the prior best results of Gilyén and Li (2019). •k-wise uniformity testingis the problem of distinguishing whether a distribution over {0, 1}nis uniform when restricted to anykcoordinates or ε-far from any such distribution. We propose the first quantum algorithm for this problem with query complexityO(√nk/ε), achieving a quadratic speedup over the state-of-the-art classical algorithm with sample complexityO(nk/ε2) by O’Donnell and Zhao (2018). Moreover, whenk= 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.
Property testing of distributions is a central topic in information theory, learning theory, and statistics. While quantum algorithms are known to offer significant speedups for property testing of a single distribution or a pair of distributions, it is unclear whether quantum algorithms provide speedups for property testing of m (m≥3) distributions. This work focuses on quantum algorithms for testing whether m distributions have similar means or are ε-far from mean similarity under two models. In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly. We design quantum algorithms with complexities O~(1/ε) (the O~ notation hides poly-logarithmic factors) and O~(m/ε) in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts. We further establish quantum lower bounds of Ω(1/ε) and $Ω\rbra{m^{1/3}+\frac{m^{1/4}}ε}$ for the query model and the sampling model, demonstrating the optimality of our quantum algorithms in terms of the dependence on ε up to logarithmic factors.
Suppose one has access to oracles generating samples from two unknown probability distributions p and q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L1-norm? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L1-distance ∥p-q∥1can be estimated with a constant precision using only O(N1/2) queries in the quantum settings, whereas classical computers need Ω(N1-o(1)) queries. We also describe quantum algorithms for testing uniformity and orthogonality with query complexity O(N1/3). The classical query complexity of these problems is known to be Ω(N1/2).
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle f:[n]→[m]. Here the probability Pf(j) of an outcome j in [m] is the fraction of its domain that f maps to j. We give quantum algorithms for testing whether two such distributions are identical or epsilon-far in L1-norm. Recently, Bravyi, Hassidim, and Harrow showed that if Pf and Pg are both unknown (i.e., given by oracles f and g), then this testing can be done in roughly sqrtm quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3 queries in the unknown-unknown case and about sqrtm queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson.
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle f:[n]→[m]. Here the probability $\PP_f(j)$ of an outcome j∈[m] is the fraction of its domain that f maps to j. We give quantum algorithms for testing whether two such distributions are identical or ε-far in L1-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles f and g), then this testing can be done in roughly m quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3 queries in the unknown-unknown case and about m queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.
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{d1/3/ε2,d1/2/ε}). Here we improve the upper bound to O(min{d1/3/ε4/3,d1/2/ε}), which we conjecture is optimal.
Recent advancements in quantum devices have posed an intriguing challenge of verifying their intended functionality.These devices, typically time-bounded, are often designed to prepare specific 𝑛-qubit states, denoted as 𝜌 ! and 𝜌 " .The problem of (tolerant) quantum state testing aims to design algorithms that can efficiently decide whether 𝜌 ! is either 𝜀 " -close to or 𝜀 # -far from 𝜌 " with respect to a chosen distance-like measure.This problem generalizes classical distribution testing to the quantum domain and forms a part of quantum property testing, an emerging field dedicated to developing efficient quantum testers for properties of quantum objects.The computational complexity of time-bounded state testing varies significantly with the choice of closeness measure, exhibiting a dichotomy-like behavior:• For both the trace distance (ℓ " norm) and the quantum (von Neumann) entropy difference, the problems correspond to the complexity class QSZK, as shown in Watrous (FOCS 2002), Watrous (SICOMP 2009), and Ben-Aroya, Schwartz, and Ta-Shma (CCC 2008), which is widely believed to be strictly more powerful than BQP.