Unitary property testing lower bounds by polynomials

Understand

We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property.

• In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum" problems that have no classical analogue.
• Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods.
• Our main contribution is a generalized polynomial method for unitary property testing problems.