Rajat Mittal, Institute for Quantum Computing (IQC)
Abstract
Quantum query complexity measures the number of input bits that must be read by a quantum algorithm to evaluate a function. Many quantum algorithms can be formulated in this query model, some of the important ones being Grover search and evaluation of NAND trees. Recently it was shown that we can construct these query algorithms from the solutions of a semidefinite program, which turns out to be dual of adversary bound. We will talk about various ways like span programs, learning graphs to give solutions for this SDP for interesting functions. These can be thought of as classical ways to give quantum query algorithms. We will compare the strength and limitations of these approaches in giving these algorithms.