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.
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.
Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.
Quantum computing represents a transformative approach to computation that exploits the principles of quantum mechanics to process information in fundamentally different ways from classical computers. Over the past few decades, the field has evolved from a primarily theoretical discipline into an active area of research spanning computer science, mathematics, physics, information theory, and engineering. As quantum technologies continue to develop, understanding the fundamental computational principles underlying quantum algorithms has become increasingly important. Foundations of Quantum Computing: The Query Model Perspective presents a systematic introduction to quantum computing with particular emphasis on the query model, a powerful framework for studying the computational complexity of quantum algorithms. The query model provides a clean and mathematically tractable setting in which the number of queries made to an unknown function or oracle can be used as the primary measure of computational cost. This perspective offers valuable insights into the capabilities and limitations of quantum computation and provides a natural foundation for understanding quantum speedups. The book introduces the fundamental concepts required to study quantum computation, including quantum states, quantum gates, quantum circuits, measurement, superposition, entanglement, and quantum algorithms. These concepts are developed alongside the query-complexity framework, enabling readers to understand how quantum algorithms exploit interference and other quantum phenomena to reduce the number of queries required to solve computational problems. Particular attention is given to important quantum query algorithms and complexity results. Classical and quantum query complexities are discussed comparatively to illustrate the sources and significance of quantum advantages. Well-known examples such as the Deutsch–Jozsa algorithm, Grover's search algorithm, and related oracle-based problems provide concrete illustrations of how quantum procedures can outperform their classical counterparts. The discussion also introduces lower-bound techniques and fundamental principles that help establish the limitations of quantum query algorithms. The query model is not only useful for understanding individual algorithms but also serves as an important bridge between quantum algorithms and computational complexity theory. By focusing on query complexity, many problems can be examined independently of the details of a particular physical implementation. This abstraction makes the framework especially useful for developing rigorous proofs, comparing computational resources, and identifying the fundamental sources of quantum advantage. This book is intended for students, researchers, educators, and professionals interested in quantum computing and theoretical computer science. It can serve as an introductory reference for readers with a background in discrete mathematics, linear algebra, algorithms, or theoretical computer science, while also providing a foundation for readers who wish to pursue more advanced studies in quantum complexity theory and quantum algorithms. The chapters have been organized to progress from foundational concepts toward more advanced aspects of the quantum query model. Mathematical formulations are accompanied by explanations and examples to help readers connect abstract theoretical ideas with computational intuition. The broader objective is to provide readers with the tools necessary not only to understand existing quantum algorithms but also to reason about new problems from a query-complexity perspective. As quantum computing continues to mature, the ability to distinguish genuine computational advantages from implementation-specific effects will become increasingly significant. The query model provides one of the clearest theoretical environments for making this distinction. By studying quantum computation through this lens, readers can develop a deeper appreciation of both the power and the limitations of quantum algorithms It is hoped that Foundations of Quantum Computing: The Query Model Perspective will serve as a useful resource for learning, teaching, and research, and will encourage further exploration into the rapidly evolving landscape of quantum computation and quantum complexity theory.
One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.
The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most q oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model:
(i) (Unbiased) Phase estimation up to a precision ε requires Θ(qε21) queries;
(ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ(qε2p(1−p)) queries;
(iii) Search among N items requires Θ(qN) queries;
(iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(qnm) queries.
All of these bounds are optimal up to a constant factor, for all q from 1, corresponding to the classical complexity, to Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor.
Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
The polynomial and the adversary methods are the two main tools for proving lower bounds on query complexity of quantum algorithms. Both methods have found a large number of applications, some problems more suitable for one method, some for the other. It is known though that the adversary method, in its general negative-weighted version, is tight for bounded-error quantum algorithms, whereas the polynomial method is not. By the tightness of the former, for any polynomial lower bound, there ought to exist a corresponding adversary lower bound. However, direct reduction was not known. In this paper, we give a simple and direct reduction from the polynomial method (in the form of a dual polynomial) to the adversary method. This shows that any lower bound in the form of a dual polynomial is actually an adversary lower bound of a specific form.