Quantum and classical query complexities of local search are polynomially related

Miklos Santha, Mario Szegedy

Research output: Contribution to journalArticle

2 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 x?" We show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. This generalizes earlier results of Aldous (Ann. Probab. 11(2):403-413, [1983]) and Aaronson (SIAM J. Comput. 35(4):804-824, [2006]) and solves the main open problem in Aaronson (SIAM J. Comput. 35(4):804-824, [2006]).

Original languageEnglish (US)
Pages (from-to)557-575
Number of pages19
JournalAlgorithmica (New York)
Issue number3
StatePublished - Nov 1 2009

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics


  • Local search
  • Quantum computing
  • Query complexity

Fingerprint Dive into the research topics of 'Quantum and classical query complexities of local search are polynomially related'. Together they form a unique fingerprint.

  • Cite this