Quantum and classical query complexities of local search are polynomially related

Miklos Santha, Mario Szegedy

Research output: Contribution to journalConference article

13 Scopus citations


Let f be an integer valued function on a finite set V. We call an undirected graph G(V, E) a neighborhood structure for f. The problem of finding a local minimum for f can be phrased as: for a fixed neighborhood structure G(V, E) find a vertex x ∈ V such that f(x) is not bigger than any value that f takes on some neighbor of x. The complexity of the algorithm is measured by the number of questions of the form "what is the value of f on z?" We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous and Aaronson and solves the main open problem in [1].

Original languageEnglish (US)
Pages (from-to)494-501
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 2004
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 15 2004


All Science Journal Classification (ASJC) codes

  • Software


  • Decision trees
  • Local optimization
  • Neighborhood structure
  • PLO
  • Quantum computationquery model

Cite this