Performance measurement and data base design
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
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 ∥1 can 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). © 2011 IEEE.
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory
Rolf Clauberg
IBM J. Res. Dev
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine