10.4230/LIPICS.STACS.2010.2450
Bravyi, Sergey
Sergey
Bravyi
Harrow, Aram W.
Aram W.
Harrow
Hassidim, Avinatan
Avinatan
Hassidim
Quantum Algorithms for Testing Properties of Distributions
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2010
Article
Quantum computing
property testing
sampling
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
2010
2010-03-09
2010-03-09
2010-03-09
en
urn:nbn:de:0030-drops-24502
10.4230/LIPIcs.STACS.2010
978-3-939897-16-3
1868-8969
10.4230/LIPIcs.STACS.2010
LIPIcs, Volume 5, STACS 2010
27th International Symposium on Theoretical Aspects of Computer Science
2013
5
13
131
142
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2010
5
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
307698 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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 $\|p-q\|_1$ can be estimated with a constant precision using only $O(N^{1/2})$ queries in the quantum settings, whereas classical computers need $\Omega(N^{1-o(1)})$ 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})$. A quantum algorithm for testing Uniformity has been recently independently discovered
by Chakraborty et al. \cite{CFMW09}.
LIPIcs, Vol. 5, 27th International Symposium on Theoretical Aspects of Computer Science, pages 131-142