Lower Bounds on Quantum Query Complexity

Abstract

Shor's and Grover's famous quantum algorithms for factoring and searching show that quantum computers can solve certain computational problems significantly faster than any classical computer. We discuss here what quantum computers_cannot_ do, and specifically how to prove limits on their computational power. We cover the main known techniques for proving lower bounds, and exemplify and compare the methods.

survey, 23 pages

References in corpus (3)

• A new quantum lower bound method, with an application to strong direct product theorem for quantum search
• A quantum lower bound for the query complexity of Simon's problem
• (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

Cited by in corpus (14)

• Negative weights make adversaries stronger
• Necessary Condition for the Quantum Adiabatic Approximation
• Quantum Walks
• On continuous variable quantum algorithms for oracle identification problems
• Quantum Computing: Lecture Notes
• A learning graph based quantum query algorithm for finding constant-size subgraphs
• Quantum exploration algorithms for multi-armed bandits
• Applications of the Adversary Method in Quantum Query Algorithms
• Unbounded Error Quantum Query Complexity
• Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
• All Quantum Adversary Methods are Equivalent
• Exact quantum lower bound for Grover's problem
• A Quantum Algorithm for the Classification of Patterns of Boolean Functions
• The quantum query complexity of learning multilinear polynomials