Quantum and classical query complexities of local search are polynomially related
Miklós Sántha, Márió Szegedy · 2004
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[4] Ald and Aaronson [1] Aar and solves the main open problem in Aar.