2026-07-20T05:48:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2860 2024-03-06T10:33:37Z ddc:004 open_access

New Results on Quantum Property Testing Chakraborty, Sourav Fischer, Eldar Matsliah, Arie de Wolf, Ronald quantum algorithm property testing We present several new examples of speed-ups 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 unknown-unknown case and about $sqrt{m}$ queries in the known-unknown 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 speed-ups, 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 constant-vs-polynomial speed-up due to Aaronson. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sourav Chakraborty and Eldar Fischer and Arie Matsliah and Ronald de Wolf 2010 Is Part Of LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2010.145 urn:nbn:de:0030-drops-28603 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.145 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode