Chakraborty, Sourav ;
Fischer, Eldar ;
Matsliah, Arie ;
de Wolf, Ronald
New Results on Quantum Property Testing
Abstract
We present several new examples of speedups 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]\to[m]$. Here the probability $P_f(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 $L_1$norm. Recently, Bravyi, Hassidim, and Harrow showed that if
$P_f$ and $P_g$ are both unknown (i.e., given by oracles $f$ and $g$), then this testing can be done in roughly $sqrt{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 $m^{1/3}$ quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about $m^{2/3}$ queries in the unknownunknown case and about $sqrt{m}$ queries in the knownunknown 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 speedups, 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 constantvspolynomial speedup due to Aaronson.
BibTeX  Entry
@InProceedings{chakraborty_et_al:LIPIcs:2010:2860,
author = {Sourav Chakraborty and Eldar Fischer and Arie Matsliah and Ronald de Wolf},
title = {{New Results on Quantum Property Testing}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages = {145156},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897231},
ISSN = {18688969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2860},
URN = {urn:nbn:de:0030drops28603},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.145},
annote = {Keywords: quantum algorithm, property testing}
}
Keywords: 

quantum algorithm, property testing 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Issue date: 

2010 
Date of publication: 

2010 