Quantum algorithms for testing properties of distributions

Details Quantum algorithms for testing properties of distributions Quantum algorithms for testing properties of distributions

2009-07-22

arxiv.org/abs/0907.3920v1

IEEE. Trans. Inf. Th., vol. 57, no. 6, pp. 3971--3981, June 2011

Physics

Quantum Physics

20 pages

Scientific paper

10.1109/TIT.2011.2134250

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 L_1-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 L_1-distance between P and Q can be estimated with a constant precision using approximately N^{1/2} queries in the quantum settings, whereas classical computers need \Omega(N) queries. We also describe quantum algorithms for testing Uniformity and Orthogonality with query complexity O(N^{1/3}). The classical query complexity of these problems is known to be \Omega(N^{1/2}).

Affiliated with

Also associated with

No associations

Rating

Quantum algorithms for testing properties of distributions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum algorithms for testing properties of distributions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum algorithms for testing properties of distributions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-354134