Quantum query complexity is a fundamental model in quantum computation, which captures known quantum algorithms such as Grover's search algorithm, and also enables rigorous comparison between classical and quantum models of computation. The polynomial method has become one of the main paradigms for proving lower bounds on quantum query complexity.
In this work, we study unitary property testing settings, which generalizes the standard quantum query complexity model and captures "inherently quantum" problems that appear to have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. We prove a generalized polynomial method for analyzing the complexity of unitary property testing problems and apply this method on new problems such as unitary recurrence time, approximate dimension counting, and estimating the entanglement entropy. Furthermore, we present a possible approach towards an oracle separation of QMA and QMA(2), which is a long-standing question in quantum complexity theory.
*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*
