Quantum Property Testing: A Survey and One New Result

QuICS Seminar

Ronald de Wolf (CWI and University of Amsterdam)
Wednesday, July 8, 2015 - 2:00pm
CSS 3100A

"Property testers" are 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 talk 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 more efficient than classical testers. We also describe one new result: a quantum algorithm for testing whether a given n-bit Boolean function f is a k-junta (i.e., depends on only k of the n input bits) using roughly sqrt{k} queries to f, which is quadratically faster than the best classical testers. Second, we may consider classical testers of quantum objects. This is the situation that arises for instance when one is trying to determine if untrusted quantum states or operations are what they are supposed to be, based only on classical input-output behavior. Finally, we may also consider quantum testers for properties of quantum objects, such as whether two states or unitaries are equal, whether a state is separable, etc.

This is based on joint work with Ashley Montanaro (survey arXiv:1310.2035) and with Andris Ambainis, Aleksanders Belovs, and Oded Regev (k-junta testing).