Average/Worst-Case Gap of Quantum Query Complexities

スポンサーリンク

概要

• 論文の詳細を見る

• 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 f, i.e., the number of inputs for which f = 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.

• 一般社団法人情報処理学会の論文
• 2009-05-04

著者

• Kazuo Iwama

  School Of Informatics Kyoto University.

• Andris Ambainis

  Institute of Mathematics and Computer Science, University of Latvia, Latvia.

• Masaki Nakanishi

  Graduate School of Information Science, NAIST.

• Harumichi Nishimura

  School of Science, Osaka Prefecture University.

• Rudy Raymond

  Tokyo Research Laboratory, IBM Japan.

• Seiichiro Tani

  NTT Communication Science Laboratories, NTT Corporation.,JST ERATO-SORST QCI Project

• Shigeru Yamashita

  College of Information Science and Engineering, Ritsumeikan University.

• Rudy Raymond

  Tokyo Research Laboratory Ibm Japan.

• Seiichiro Tani

  Ntt Communication Science Laboratories Ntt Corporation. Jst Erato-sorst Qci Project

• Harumichi Nishimura

  School Of Science Osaka Prefecture University.

• Andris Ambainis

  Institute Of Mathematics And Computer Science University Of Latvia Latvia.

• Shigeru Yamashita

  College Of Information Science And Engineering Ritsumeikan University.

• Masaki Nakanishi

  Graduate School Of Information Science Naist.

関連論文

• Average/Worst-Case Gap of Quantum Query Complexities
• Quantum Communication Protocols with Public Coins

スポンサーリンク