Query complexity studies the amount of information about an input that is needed to solve a computational problem. This thesis investigates query complexity in several settings, with applications to cryptography and property testing, as well as connections to communication complexity and other computational models. In property testing, we study tolerant junta testing and establish the first superpolynomial quantum advantage for this problem: within a certain parameter regime, a quantum algorithm uses polynomially many queries, whereas every classical randomised algorithm requires quasipolynomially many queries. In cryptography, we study the average-case complexity of search problems. We show that verifiable delay functions do not exist in the random oracle model, and strengthen known barriers to constructing average-case hard TFNP problems from one-way functions. Finally, we study lower bounds and their behaviour across computational models. We prove new direct sum results for randomised parity decision trees. We also establish a new separation between query complexity measures of total Boolean functions and, through query-to-communication lifting, derive new communication lower bounds and lower bounds for unambiguous finite automata.
Quantum query complexity is a fundamental model for analyzing the computational power of quantum algorithms. It has played a key role in characterizing quantum speedups, from early breakthroughs such as Grover's and Simon's algorithms to more recent developments in quantum cryptography and complexity theory. This document provides a structured introduction to quantum query lower bounds, focusing on four major techniques: the hybrid method, the polynomial method, the recording method, and the adversary method. Each method is developed from first principles and illustrated through canonical problems. Additionally, the document discusses how the adversary method can be used to derive upper bounds, highlighting its dual role in quantum query complexity. The goal is to offer a self-contained exposition accessible to readers with a basic background in quantum computing, while also serving as an entry point for researchers interested in the study of quantum lower bounds.
A collision for a function
f is two distinct inputs
x1=x2 such that
f outputs the same value on both inputs:
f(x1)=f(x2). The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be
Θ(N1/3); however, these results do not apply to random functions. The issues are two-fold. First, the
Ω(N1/3) lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to
r-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of
Θ(N1/3) holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal
Ω(M1/3) lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.