Average/Worst-Case Gap of Quantum Query Complexities

• Item type: SIG Technical Reports(1)
• 公開日: 2009-05-04
• タイトル: Average/Worst-Case Gap of Quantum Query Complexities
• タイトル / 言語: en
• タイトル: Average/Worst-Case Gap of Quantum Query Complexities
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 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.
• 著者所属(英): en
• 著者所属(英): Institute of Mathematics and Computer Science, University of Latvia, Latvia.
• 著者所属(英): en
• 著者所属(英): School of Informatics, Kyoto University.
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science, NAIST.
• 著者所属(英): en
• 著者所属(英): School of Science, Osaka Prefecture University.
• 著者所属(英): en
• 著者所属(英): Tokyo Research Laboratory, IBM Japan.
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories, NTT Corporation.,JST ERATO-SORST QCI Project
• 著者所属(英): en
• 著者所属(英): College of Information Science and Engineering, Ritsumeikan University.
• 著者名: Andris, Ambainis; Kazuo, Iwama; Masaki, Nakanishi; Harumichi, Nishimura; Rudy, Raymond; Seiichiro, Tani; Shigeru, Yamashita
• 著者名(英): Andris, Ambainis; Kazuo, Iwama; Masaki, Nakanishi; Harumichi, Nishimura; Rudy, Raymond; Seiichiro, Tani; Shigeru, Yamashita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009-AL-124, 号 8, p. 1-7, 発行日 2009-05-04
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会