Applications of the Adversary Method in Quantum Query Algorithms

Understand

In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds.

• Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs.
• * We use learning graphs to improve quantum query complexity of the triangle detection and the $k$-distinctness problems.
• * We prove tight lower bounds for the $k$-sum and the triangle sum problems.