2021-07-31T11:32:52Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000621242020-04-01T00:33:29Z01164:02592:05623:05682
Average/Worst-Case Gap of Quantum Query ComplexitiesAverage/Worst-Case Gap of Quantum Query Complexitiesenghttp://id.nii.ac.jp/1001/00062124/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=62124&item_no=1&attribute_id=1&file_no=1Copyright (c) 2009 by the Information Processing Society of JapanInstitute 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 ProjectCollege of Information Science and Engineering, Ritsumeikan University.Andris, AmbainisKazuo, IwamaMasaki, NakanishiHarumichi, NishimuraRudy, RaymondSeiichiro, TaniShigeru, YamashitaThe 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-1248172009-05-042009-08-19