|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
(Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids | | Shengyu Zhang
; | | Date: |
12 Apr 2005 | | Subject: | quant-ph | | Abstract: | 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}(loglog N)^{3/2})$ on the quantum query complexity, which implies that Local Search on grids exhibits different properties at low dimensions. | | Source: | arXiv, quant-ph/0504085 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER