Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs

Details Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs

2008-06-20

arxiv.org/abs/0806.3437v1

Physics

Quantum Physics

Scientific paper

We study the problem of \emph{local search} on a graph. Given a real-valued black-box function f on the graph's vertices, this is the problem of determining a local minimum of f--a vertex v for which f(v) is no more than f evaluated at any of v's neighbors. In 1983, Aldous gave the first strong lower bounds for the problem, showing that any randomized algorithm requires $\Omega(2^{n/2 - o(1)})$ queries to determine a local minima on the n-dimensional hypercube. The next major step forward was not until 2004 when Aaronson, introducing a new method for query complexity bounds, both strengthened this lower bound to $\Omega(2^{n/2}/n^2)$ and gave an analogous lower bound on the quantum query complexity. While these bounds are very strong, they are known only for narrow families of graphs (hypercubes and grids). We show how to generalize Aaronson's techniques in order to give randomized (and quantum) lower bounds on the query complexity of local search for the family of vertex-transitive graphs. In particular, we show that for any vertex-transitive graph G of N vertices and diameter d, the randomized and quantum query complexities for local search on G are $\Omega(N^{1/2}/d\log N)$ and $\Omega(N^{1/4}/\sqrt{d\log N})$, respectively.

Affiliated with

Also associated with

No associations

Rating

Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-371573