文章基本信息
- 标题：Quantum Adversary Lower Bound for Element Distinctness with Small Range
- 本地全文：下载
- 作者：Ansis Rosmanis
- 期刊名称：Chicago Journal of Theoretical Computer Science
- 印刷版ISSN：1073-0486
- 出版年度：2014
- 卷号：2014
- 出版社：MIT Press ; University of Chicago, Department of Computer Science
- 摘要：The Element Distinctness problem is to decide whether each character of an input string is unique. The quantum query complexity of Element Distinctness is known to be $\Theta(N^{2/3})$; the polynomial method gives a tight lower bound for any input alphabet, while a tight adversary construction was only known for alphabets of size $\Omega(N^2)$.
We construct a tight $\Omega(N^{2/3})$ adversary lower bound for Element Distinctness with minimal non-trivial alphabet size, which equals the length of the input. This result may help to improve lower bounds for other related query problems
