Quantum Query Complexity of Almost All Functions with Fixed On-set Size |
| |
| Authors: | Andris Ambainis Kazuo Iwama Masaki Nakanishi Harumichi Nishimura Rudy Raymond Seiichiro Tani Shigeru Yamashita |
| |
| Affiliation: | 1.Institute of Mathematics and Computer Science,University of Latvia,Riga,Latvia;2.School of Informatics,Kyoto University,Kyoto,Japan;3.Faculty of Education Art and Science,Yamagata University,Yamagata,Japan;4.Graduate School of Information Science,Nagoya University,Nagoya,Japan;5.IBM Research - Tokyo,IBM Japan,Tokyo,Japan;6.NTT Communication Science Laboratories,NTT Corporation,Atsugi,Japan;7.College of Information Science and Engineering,Ritsumeikan University,Kusatsu,Japan |
| |
| Abstract: | This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\)-variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\), where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N}\right)}\) for a constant \({c > 0}\). This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\): \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N}\right)}\). In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
