### Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 494-501 |

Number of pages | 8 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

State | Published - Jan 1 2004 |

Event | Proceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States Duration: Jun 13 2004 → Jun 15 2004 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

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

### Cite this

}

**Quantum and classical query complexities of local search are polynomially related.** / Santha, Miklos; Szegedy, Mario.

Research output: Contribution to journal › Conference article

TY - JOUR

T1 - Quantum and classical query complexities of local search are polynomially related

AU - Santha, Miklos

AU - Szegedy, Mario

PY - 2004/1/1

Y1 - 2004/1/1

N2 - 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].

AB - 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].

KW - Decision trees

KW - Local optimization

KW - Neighborhood structure

KW - PLO

KW - Quantum computationquery model

UR - http://www.scopus.com/inward/record.url?scp=4544268402&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4544268402&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:4544268402

SP - 494

EP - 501

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

SN - 0734-9025

ER -