Alexander Belov, Institute for Quantum Computing (IQC)
Abstract
Quantum query complexity measures the complexity of a quantum algorithm by the number of queries to the input it uses. A number of strong lower bound methods for quantum query complexity have been developed. One of them is the adversary bound, first time formulated by Ambainis and later generalized by Hoyer et al. The latter, (general) adversary bound was shown to be tight by Reichardt et al. The adversary bound admits a formulation as a semi-denite program (SDP), hence, any feasible solution for its dual is an upper bound on
quantum query complexity, and this bound is also tight! For functions with Boolean input, the dual SDP can be represented as a span program. In principle, this means that span programs give an optimal quantum algorithm for any Boolean function. However, their actual applications have been mostly limited to formula evaluation. We show how to use them for another class of functions: the ones having small 1-certificates. We are going to review the basic quantum algorithms, such as Grover search, the collision and the element distinctness problems from the point of view of span programs. We finish the talk with the $O(n^{35/27})$-query quantum algorithm for the triangle problem, that is better than the best previously known algorithm by Magniez at el. using $O(n^{13/10})$ queries.