Lance Fortnow (NEC Research Institute):
Quantum Property Testing
A language L has a property tester if there exists a probabilistic
algorithm that given an input x only asks 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 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.