Bravyi, Sergey ;
Harrow, Aram W. ;
Hassidim, Avinatan
Quantum Algorithms for Testing Properties of Distributions
Abstract
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 $\pq\_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^{1o(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}.
BibTeX  Entry
@InProceedings{bravyi_et_al:LIPIcs:2010:2450,
author = {Sergey Bravyi and Aram W. Harrow and Avinatan Hassidim},
title = {{Quantum Algorithms for Testing Properties of Distributions}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {131142},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2450},
URN = {urn:nbn:de:0030drops24502},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2450},
annote = {Keywords: Quantum computing, property testing, sampling}
}
2010
Keywords: 

Quantum computing, property testing, sampling 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2010 
Date of publication: 

2010 