Understanding Quantum Algorithms via Query Complexity

Query complexity is a model of computation in which we have to compute a function $f(x_1,\dots ,x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover’s quantum search and a key subroutine of Shor’s factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we survey these results and related work, including:

• the biggest quantum-vs-classical gap for partial functions (a problem solvable with 1 query quantumly but requiring $\mathrm{\Omega }(\sqrt{N})$ queries classically);
• the biggest quantum-vs-determistic and quantum-vs-probabilistic gaps for total functions (for example, a problem solvable with $M$ queries quantumly but requiring $\tilde{\mathrm{\Omega }}(M^{2.5})$ queries probabilistically);
• the biggest probabilistic-vs-deterministic gap for total functions (a problem solvable with $M$ queries probabilistically but requiring $\tilde{\mathrm{\Omega }}(M^2)$ queries deterministically);
• the bounds on the gap that can be achieved for subclasses of functions (for example, symmetric functions);
• the connections between query algorithms and approximations by low-degree polynomials.