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.

,
SIAM
SIAM Journal on Computing
Quantum Information Processing
Quantum Computing and Advanced System Research

Buhrman, H., Fortnow, L., Newman, I., & Röhrig, H. (2008). Quantum Property Testing. SIAM Journal on Computing, 37(5), 1387–1400.