Lower bounds for local search by quantum arguments

The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube 0,1^<i>n</i>, we show a lower bound of Ω(2^<i>n</i>/4/<i>n</i>) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis's quantum adversary method, also yields a lower bound of Ω(2^<i>n</i>/2/<i>n</i>²) on the problem's <i>classical</i> randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension <i>d</i>≥3.

• Publication year

  2003

• Venue

  Symposium on the Theory of Computing

• Publication date

  2003-07-21

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1145/1007352.1007358arXiv quant-ph/0307149
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Quantum and Classical Query Complexities of Local Search Are Polynomially Related

  2004cited by this paper
• All Quantum Adversary Methods are Equivalent

  2004cited by this paper
• Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

  2004cited by this paper
• Lower bounds for randomized and quantum query complexity using Kolmogorov arguments

  2003cited by this paper
• Polynomial degree vs. quantum query complexity

  2003influential reference
• Complexity measures and decision tree complexity: a survey

  2002cited by this paper
• Exponential lower bound for 2-query locally decodable codes via a quantum argument

  2002cited by this paper
• How powerful is adiabatic quantum computation?

  2001cited by this paper
• Quantum lower bound for the collision problem

  2001influential reference
• Quantum lower bounds for the collision and the element distinctness problems

  2001cited by this paper
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

  2001cited by this paper
• Quantum lower bounds by quantum arguments

  2000cited by this paper
• Bounds for small-error and zero-error quantum algorithms

  1999cited by this paper
• Quantum lower bounds by polynomials

  1998cited by this paper
• Strengths and Weaknesses of Quantum Computing

  1997cited by this paper
• A Quantum Algorithm for Finding the Minimum

  1996cited by this paper
• Randomized Algorithms: Tail Inequalities

  1995cited by this paper
• Dividing and Conquering the Square

  1993cited by this paper
• Erratum: Local Optimization on Graphs

  1993influential reference
• On Total Functions, Existence Theorems and Computational Complexity

  1991influential reference
• Local optimization on graphs

  1989cited by this paper
• How Easy is Local Search?

  1985cited by this paper
• Minimization Algorithms and Random Walk on the $d$-Cube

  1983influential reference
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

  1975cited by this paper
• Relativizations of the P =? NP Question

  1975influential reference

• The Query Complexity of Local Search in Rounds on General Graphs

  2026cites this paper
• Complexity of learning matchings and half graphs via edge queries

  2025influential citation
• Tarski Lower Bounds from Multi-Dimensional Herringbones

  2025cites this paper
• Parameterized Quantum Query Algorithms for Graph Problems

  2024cites this paper
• Randomized Lower Bounds for Tarski Fixed Points in High Dimensions

  2024cites this paper
• The randomized query complexity of finding a Tarski fixed point on the Boolean hypercube

  2024cites this paper
• Total NP Search Problems with Abundant Solutions

  2024cites this paper
• The Sharp Power Law of Local Search on Expanders

  2023influential citation
• IUScholarWorks at Indiana University South Bend The Time Complexity of A* with Approximate Heuristics on Multiple-Solution Search Spaces

  2023cites this paper
• Improved Algorithm and Lower Bound for Variable Time Quantum Search

  2023cites this paper
• Certificate Games and Consequences for the Classical Adversary Bound

  2022influential citation
• Smoothed Online Learning is as Easy as Statistical Learning

  2022cites this paper
• A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs

  2021influential citation
• Quantum Computing: Applications and Future Importance

  2021cites this paper
• The Query Complexity of Local Search and Brouwer in Rounds

  2020influential citation
• Unconditional Lower Bounds for Adaptive Massively Parallel Computation

  2020influential citation
• How to trap a gradient flow

  2020influential citation
• On query-to-communication lifting for adversary bounds

  2020cites this paper
• Representing fitness landscapes by valued constraints to understand the complexity of local search

  2019cites this paper
• The Problem of Dynamic Programming on a Quantum Computer

  2019cites this paper
• Limitations of Quantum Walks and Randomized Algorithms

  2019cites this paper
• J un 2 01 9 Quantum Algorithms for Solving Dynamic Programming Problems

  2019cites this paper
• Discrete logarithm and Diffie-Hellman problems in identity black-box groups

  2019cites this paper
• The communication complexity of local search

  2018cites this paper
• All Classical Adversary Methods Are Equivalent for Total Functions

  2017cites this paper
• Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

  2017cites this paper
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems

  2017cites this paper
• Nearly optimal separations between communication (or query) complexity and partitions

  2015cites this paper
• Separations in query complexity using cheat sheets

  2015cites this paper
• Separating decision tree complexity from subcube partition complexity

  2015cites this paper
• The computational power of optimization in online learning

  2015influential citation
• Application of Grover's Quantum Search Algorithm to Solve the Transcendental Logarithm Problem

  2014cites this paper
• Efficient algorithms in quantum query complexity

  2014cites this paper
• Evolutionary Algorithms for Quantum Computers

  2013cites this paper
• Quantum Algorithms for Atomic Clocks

  2013cites this paper
• The Time Complexity of A* with Approximate Heuristics on Multiple-Solution Search Spaces

  2012cites this paper
• Toward a complexity theory for randomized search heuristics

  2011cites this paper
• Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

  2011cites this paper
• Ranking-Based Black-Box Complexity

  2011cites this paper
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization

  2011cites this paper
• Can quantum search accelerate evolutionary algorithms?

  2010influential citation
• Time Space Tradeoffs for Attacks against One-Way Functions and PRGs

  2010cites this paper
• Postselection Finite Quantum Automata

  2010cites this paper
• Parallel Search Optimization for Storage Virtualization

  2010cites this paper
• Quantum Query Complexity of Minor-Closed Graph Properties

  2010influential citation
• The Partition Bound for Classical Communication Complexity and Query Complexity

  2009cites this paper
• Quantum Proofs for Classical Theorems

  2009cites this paper
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function

  2009cites this paper
• A note on the sign degree of formulas

  2009cites this paper
• Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

  2009cites this paper
• On Finding Sensitivity of Quantum and Classical Gates

  2009cites this paper
• Tight Bounds for Randomized and Quantum Local Search

  2009influential citation
• Quantum and randomized lower bounds for local search on vertex-transitive graphs

  2008influential citation
• A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions

  2008cites this paper
• Quantum Query Complexity of Boolean Functions with Small On-Sets

  2008cites this paper
• Adversary Lower Bounds for Nonadaptive Quantum Algorithms

  2008cites this paper
• The Complexity Zoo

  2008cites this paper
• Quantum Separation of Local Search and Fixed Point Computation

  2008cites this paper
• A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions

  2008cites this paper
• Adversary lower bounds for nonadaptive quantum algorithms

  2008cites this paper
• Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory

  2007cites this paper
• Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation

  2007influential citation
• Parameterized Proof Complexity

  2007cites this paper
• Quantum Circuit Design and Analysis for Database Search Applications

  2007cites this paper
• Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation

  2007influential citation
• Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument

  2007cites this paper
• Scalability, Complexity and Reliability in Quantum Information Processing

  2007cites this paper
• The Limits of Quantum Computers

  2007cites this paper
• On the Value of Good Advice: The Complexity of A* Search with Accurate Heuristics

  2007cites this paper
• New upper and lower bounds for randomized and quantum local search

  2006influential citation
• On the Probabilistic Query Complexity of Transitively Symmetric Problems

  2006cites this paper
• Lattice Problems in NP ∩ coNP Dorit Aharonov

  2006cites this paper
• On the Quantum Query Complexity of Local Search in Two and Three Dimensions

  2006influential citation
• Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs

  2006cites this paper
• Lower Bounds Using Kolmogorov Complexity

  2006cites this paper
• Lattice problems in NP ∩ coNP

  2005cites this paper
• On the complexity of Sperner’s Lemma

  2005cites this paper
• Enhanced algorithms for Local Search

  2005influential citation
• Lower Bounds on Matrix Rigidity Via a Quantum Argument

  2005cites this paper
• Logical approaches to the complexity of search problems: : proof complexity, quantified propositional calculus, and bounded arithmetic

  2005cites this paper
• Lower Bounds on Quantum Query Complexity

  2005cites this paper
• (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids

  2005influential citation
• On the Black-Box Complexity of Sperner’s Lemma

  2005cites this paper
• THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS

  2005cites this paper
• On the power of Ambainis lower bounds

  2005cites this paper
• Quantum search algorithms

  2004influential citation
• Quantum Identification of Boolean Oracles

  2004cites this paper
• Quantum computing, postselection, and probabilistic polynomial-time

  2004cites this paper
• Lattice Problems in NP cap coNP

  2004cites this paper
• Limits on Efficient Computation in the Physical World

  2004cites this paper
• Quantum and Classical Query Complexities of Local Search Are Polynomially Related

  2004influential citation
• Quantum encodings and applications to locally decodable codes and communication complexity

  2004cites this paper
• Lower bounds for randomized and quantum query complexity using Kolmogorov arguments

  2003influential citation
• Polynomial degree vs. quantum query complexity

  2003cites this paper
• On the Power of Ambainis's Lower Bounds

  2003cites this paper
• CS 860 Lecture 12 — June 13 Spring 2006 2 Lower Bound For Triangle Problem

  year unknowncites this paper