期刊
ALGORITHMICA
卷 34, 期 4, 页码 429-448出版社
SPRINGER
DOI: 10.1007/s00453-002-0976-3
关键词
quantum computation; searching; sorting; element distinctness; lower bound
We consider the quantum complexities of the following three problems: searching an ordered list, sorting an un-ordered list, and deciding whether the numbers in a list are all distinct. Letting N be the number of elements in the input list, we prove a lower bound of (1/pi) (ln(N) - 1) accesses to the list elements for ordered searching, a lower bound of Omega (N log N) binary comparisons for sorting, and a lower bound of Omega (rootN log N) binary comparisons for element distinctness. The previously best known lower bounds are 1/12 log(2)(N) - O(1) due to Ambainis, Omega (N), and Omega (rootN), respectively. Our proofs are based on a weighted all-pairs inner product argument. In addition to our lower bound results, we give an exact quantum algorithm for ordered searching using roughly 0.631 log(2)(N) oracle accesses. Our algorithm uses a quantum routine for traversing through a binary search tree faster than classically, and it is of a nature very different from a faster exact algorithm due to Farhi, Goldstone, Gutmann, and Sipser.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据