Theory of Computing Library Graduate Surveys
---------------------------------------------------
Title     : A Survey of Quantum Property Testing
Authors   : Ashley Montanaro and Ronald de Wolf
Number    : 7
Pages     : 1-81
URL       : https://theoryofcomputing.org/articles/gs007

Abstract
--------

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.