The Rank Method and Applications to Quantum Lower Bounds
In the oracle interrogation problem, we are allowed to make q queries to an unknown oracle H, and
attempt to produce k input/output pairs of H. If only classical queries are allowed, then this problem
is trivial when q is at most k, but impossible otherwise. Once we allow queries on a quantum superposition
of inputs, however, little was previously known. In our recent paper, we introduce a new quantum lower
bound technique, called the Rank Method, and use it to prove exact lower bounds for the oracle interrogation
problem in the quantum world. In this talk, I will give the intuition behind the Rank Method and some
applications.
Stanford Theory Lunch
