A language $L$ has a property tester if there exists a probabilistic algorithm that given an input $x$ queries only a small number of bits of $x$ and distinguishes the cases as to whether $x$ is in $L$ and $x$ has large Hamming distance from all $y$ in $L$. We define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.
A language L has a property tester if there exists a probabilistic algorithm that given an input x queries only a small number of bits of x and distinguishes the cases as to whether x is in L and x has large Hamming distance from all y in L. We define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.
A language L has a property tester if there exists a probabilistic algorithm that given an input x queries only a small number of bits of x and distinguishes the cases as to whether x is in L and x has large Hamming distance from all y in L. We define a similar notion of quantum property testing and show that there exist languages with good quantum property testers but no good classical testers. We also show there exist languages which require a large number of queries even for quantumly testing.
The area of property testing tries to design algorithms that can efficiently handle very large amounts of data: given a large object that either has a certain property or is somehow “far” from having that property, a tester should efficiently distinguish between these two cases. In this survey we describe recent results obtained for quantum property testing. This area naturally falls into three parts. First, we may consider quantum testers for properties of classical objects. We survey the main examples known where quantum testers can be much (sometimes exponentially) more efficient than classical testers. Second, we may consider classical testers of quantum objects. These arise for instance when one is trying to determine if quantum states or operations do what they are supposed to do, based only on classical input-output behavior. Finally, we may also consider quantum testers for properties of quantum objects, such as states or operations. We survey known bounds on testing various natural properties, such as whether two states are equal, whether a state is separable, whether two operations commute, etc. We also highlight connections to other areas of quantum information theory and mention a number of open questions.
We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property Π and reject inputs that are ε -far from Π , while only probing a minuscule portion of their input.We investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody, and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity. This also resolves a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing, 2016).Our algorithmic results include a purpose an algorithmic framework that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable . A consequence of this framework is a QMA algorithm to verify the Parity of an n -bit string with O(n2/3) queries and proof length. We also propose a QMA algorithm for testing graph bipartitneness, a property that lies outside of this family, for which there is a quantum speedup.
Property testing of distributions is a central topic in information theory, learning theory, and statistics. While quantum algorithms are known to offer significant speedups for property testing of a single distribution or a pair of distributions, it is unclear whether quantum algorithms provide speedups for property testing of m (m≥3) distributions. This work focuses on quantum algorithms for testing whether m distributions have similar means or are ε-far from mean similarity under two models. In the query model, the algorithm can choose which distribution to sample from, whereas in the sampling model, the distributions are selected uniformly. We design quantum algorithms with complexities O~(1/ε) (the O~ notation hides poly-logarithmic factors) and O~(m/ε) in the query and sampling models, respectively, achieving quadratic speedups over the classical counterparts. We further establish quantum lower bounds of Ω(1/ε) and $Ω\rbra{m^{1/3}+\frac{m^{1/4}}ε}$ for the query model and the sampling model, demonstrating the optimality of our quantum algorithms in terms of the dependence on ε up to logarithmic factors.
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]→[m]. Here the probability $\PP_f(j)$ of an outcome j∈[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 ε-far in L1-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles f and g), then this testing can be done in roughly 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 m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3 queries in the unknown-unknown case and about 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 \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.
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]→[m]. Here the probability Pf(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 L1-norm. Recently, Bravyi, Hassidim, and Harrow showed that if Pf and Pg are both unknown (i.e., given by oracles f and g), then this testing can be done in roughly sqrtm quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3 queries in the unknown-unknown case and about sqrtm 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.