Quantum query complexity

A proxy for time-complexity of an algorithm is the number of bits of the input it reads in the worst-case, the so-called query complexity.

Quantum algorithms can query input strings in superposition which can sometimes lead to much faster algorithms such as Shor's algorithm for integer factorization. Understanding quantum query complexity is one of the major challenges of quantum computing. This project is about exploiting a recently-discovered characterization of quantum query complexity in terms of polynomials. Fourier analysis of boolean functions and the theory of semidefinite programming (a generalization of linear programming) have given powerful tools to study crude bounds on quantum query complexity in terms of polynomials. In this project, these tools will be sharpened using analytic and operator-space theoretic techniques.