Physics – Quantum Physics
Scientific paper
2005-04-12
Physics
Quantum Physics
18 pages, 1 figure. v2: introduction rewritten, references added. v3: a line for grant added. v4: upper bound section rewritte
Scientific paper
The Local Search problem, which finds a local minimum of a black-box function on a given graph, is of both practical and theoretical importance to many areas in computer science and natural sciences. In this paper, we show that for the Boolean hypercube $\B^n$, the randomized query complexity of Local Search is $\Theta(2^{n/2}n^{1/2})$ and the quantum query complexity is $\Theta(2^{n/3}n^{1/6})$. We also show that for the constant dimensional grid $[N^{1/d}]^d$, the randomized query complexity is $\Theta(N^{1/2})$ for $d \geq 4$ and the quantum query complexity is $\Theta(N^{1/3})$ for $d \geq 6$. New lower bounds for lower dimensional grids are also given. These improve the previous results by Aaronson [STOC'04], and Santha and Szegedy [STOC'04]. Finally we show for $[N^{1/2}]^2$ a new upper bound of $O(N^{1/4}(\log\log N)^{3/2})$ on the quantum query complexity, which implies that Local Search on grids exhibits different properties at low dimensions.
No associations
LandOfFree
(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids 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 (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-350472