Table of contents

Classical and Quantum Query Complexity

From decision-tree foundations to modern adversary methods, span programs, and research frontiers in quantum algorithms

Read each section in order. Every title can be opened as a TheoryTrace document.

• Cover
• Copyright
• How to read this book
• Introduction
• Chapter 1: The Query Model as a Theory of Information Access
• Chapter 2: Mathematical Foundations for Query Complexity
• Chapter 3: Deterministic Decision Trees
• Chapter 4: Randomized Query Algorithms
• Chapter 5: Classical Lower-Bound Methods
• Chapter 6: Boolean Function Measures and Structural Complexity
• Chapter 7: The Polynomial Method in Classical Query Complexity
• Chapter 8: Quantum Computation Preliminaries
• Chapter 9: The Quantum Query Model
• Chapter 10: First Quantum Query Algorithms
• Chapter 11: Grover Search and Amplitude Amplification
• Chapter 12: Quantum Lower Bounds I: The Polynomial Method
• Chapter 13: Approximate Degree in Depth
• Chapter 14: Quantum Lower Bounds II: Hybrid and Adversary Methods
• Chapter 15: The General Adversary Bound
• Chapter 16: Span Programs and Algorithm Design
• Chapter 17: Composition, Direct Sums, and Product Phenomena
• Chapter 18: Total Functions, Partial Functions, and Separations
• Chapter 19: Query Complexity of Graph, Property, and Symmetry Problems
• Chapter 20: Quantum Walks and Query Algorithms
• Chapter 21: Learning Graphs, Certificate Structures, and Advanced Algorithmic Frameworks
• Chapter 22: Beyond Boolean Functions: Relations, State Conversion, and Nonstandard Oracles
• Chapter 23: Connections to Communication Complexity, Learning Theory, and Cryptography
• Chapter 24: Research Frontiers in Classical and Quantum Query Complexity
• Conclusion