|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size | | Andris Ambainis
; Kazuo Iwama
; Masaki Nakanishi
; Harumichi Nishimura
; Rudy Raymond
; Seiichiro Tani
; Shigeru Yamashita
; | | Date: |
18 Aug 2009 | | Abstract: | This paper considers the query complexity of the functions in the family
F_{N,M} of N-variable Boolean functions with onset size M, i.e., the number of
inputs for which the function value is 1, where 1<= M <= 2^{N}/2 is assumed
without loss of generality because of the symmetry of function values, 0 and 1.
Our main results are as follows: (1) There is a super-linear gap between the
average-case and worst-case quantum query complexities over F_{N,M} for a
certain range of M. (2) There is no super-linear gap between the average-case
and worst-case randomized query complexities over F_{N,M} for every M. (3) For
every M bounded by a polynomial in N, any function in F_{N,M} has quantum query
complexity Theta (sqrt{N}). (4) For every M=O(2^{cN}) with an arbitrary large
constant c<1, any function in F_{N,M} has randomized query complexity Omega
(N). | | Source: | arXiv, 0908.2468 | | 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