Quantum and classical query complexities of local search are polynomially related

Miklos Santha, Mario Szegedy

Research output: Contribution to journalArticle

2 Citations (Scopus)

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 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)
Volume55
Issue number3
DOIs
StatePublished - Nov 1 2009

Fingerprint

Query Complexity
Local Search
G-structures
Local Minima
Undirected Graph
Finite Set
Open Problems
Generalise
Integer
Vertex of a graph
Form

All Science Journal Classification (ASJC) codes

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

Keywords

  • Local search
  • Quantum computing
  • Query complexity

Cite this

@article{b4a2b159ff5e46aaacda82474d592bd5,
title = "Quantum and classical query complexities of local search are polynomially related",
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 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]).",
keywords = "Local search, Quantum computing, Query complexity",
author = "Miklos Santha and Mario Szegedy",
year = "2009",
month = "11",
day = "1",
doi = "10.1007/s00453-008-9169-z",
language = "English (US)",
volume = "55",
pages = "557--575",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "3",

}

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

In: Algorithmica (New York), Vol. 55, No. 3, 01.11.2009, p. 557-575.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Santha, Miklos

AU - Szegedy, Mario

PY - 2009/11/1

Y1 - 2009/11/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 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]).

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

KW - Local search

KW - Quantum computing

KW - Query complexity

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

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

U2 - 10.1007/s00453-008-9169-z

DO - 10.1007/s00453-008-9169-z

M3 - Article

AN - SCOPUS:67650698550

VL - 55

SP - 557

EP - 575

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 3

ER -