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.
Simon's problem asks the following: determine if a function f:{0,1}n→{0,1}n is one-to-one or if there exists a unique s∈{0,1}n such that f(x)=f(x⊕s) for all x∈{0,1}n, given the promise that exactly one of the two holds. A classical algorithm that can solve this problem for every f requires 2Ω(n) queries to f. Simon showed that there is a quantum algorithm that can solve this promise problem for every f using only O(n) quantum queries to f. A matching lower bound on the number of quantum queries was given by Koiran et al., even for functions f:Fpn→Fpn. We give a short proof that O(n) quantum queries is optimal even when we are additionally promised that f is linear. This is somewhat surprising because for linear functions there even exists a classical n-query algorithm.
In this paper, we introduce the hybrid query complexity, denoted as Q(f;q), which is the minimal query number needed to compute f, when a classical decision tree is allowed to call q′-query quantum subroutines for any q′≤q. We present the following results: ∙ There exists a total Boolean function f such that Q(f;1)=O(R(f)4/5). ∙Q(f;q)=Ω(bs(f)/q+bs(f)) for any Boolean function f; the lower bound is tight when f is the OR function. ∙Q(g∘XORClogn;1)=Ω(n) for some sufficiently large constant C, where g:=BOOLSIMONn is a variant of Simon's problem. Note that Q(g∘XORClogn)=O(polylogn). Therefore an exponential separation is established. Furthermore, this open the road to prove the conjecture ∀k,Q(g∘XORClogk+1n;logkn)=Ω(n), which would imply the oracle separation HP(QSIZE(nα))O⊊BQPO for any α, where HP(QSIZE(nα)) is a complexity class that contains BQTIME(nα)BPP and BPPBQTIME(nα) in any relativized world.