http://swrc.ontoware.org/ontology#TechnicalReport
Average/Worst-Case Gap of Quantum Query Complexities
en
Institute of Mathematics and Computer Science, University of Latvia, Latvia.
School of Informatics, Kyoto University.
Graduate School of Information Science, NAIST.
School of Science, Osaka Prefecture University.
Tokyo Research Laboratory, IBM Japan.
NTT Communication Science Laboratories, NTT Corporation.,JST ERATO-SORST QCI Project
College of Information Science and Engineering, Ritsumeikan University.
Andris Ambainis
Kazuo Iwama
Masaki Nakanishi
Harumichi Nishimura
Rudy Raymond
Seiichiro Tani
Shigeru Yamashita
The difference between average-case and worst-case complexities is one of the central topics in theoretical computer science, and it has been extensively studied for decades. In the quantum setting, however, only a few results are known. This paper shows a super-linear tight gap between the average-case and worst-case quantum query complexities over the families of Boolean functions defined by a natural parameter. More concretely, we consider the size of the on-set of a Boolean function ｆ, i.e., the number of inputs for which ｆ = 1, as the parameter, and give the tight gap over the families of N-variable Boolean functions with on-set size M for poly (N) < M < 2N /2.
The difference between average-case and worst-case complexities is one of the central topics in theoretical computer science, and it has been extensively studied for decades. In the quantum setting, however, only a few results are known. This paper shows a super-linear tight gap between the average-case and worst-case quantum query complexities over the families of Boolean functions defined by a natural parameter. More concretely, we consider the size of the on-set of a Boolean function ｆ, i.e., the number of inputs for which ｆ = 1, as the parameter, and give the tight gap over the families of N-variable Boolean functions with on-set size M for poly (N) < M < 2N /2.
AN1009593X
研究報告アルゴリズム（AL）
2009-AL-124
8
1-7
2009-05-04