Quantum Property 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