In this talk I will talk about the power of quantum proofs in the framework of quantum query complexity. Specifically, I will discuss the trade-off between the number of queries to an input string and the number of qubits of a quantum proof needed to verify whether the input string possesses a property of interest, and how this trade-off is affected if we only require the algorithm to output the correct answer on a fraction of the inputs. This latter question relates to the power of quantum complexity classes with access to random oracles, and specifically to the conjecture that the complexity class QMA with access to a random oracle is no more powerful than the complexity class QAM.

This talk is based on ongoing work with Alessandro Cosentino and John Watrous from the University of Waterloo.