We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N^ 2 3 ) query quantum algorithm. This improves the previous O(N^ 3 4 ) query quantum algorithm of Buhrman this http URL. (quant-ph 0007016) and matches the lower bound by Shi (quant-ph 0112086). The algorithm also solves the generalization of element distinctness in which we have to find k equal items among N items. For this problem, we get an O(N^ k (k+1) ) query quantum algorithm.
In the usual query model (where one query gives one value of @math ), it is easy to see that @math queries are also necessary. Classical lower bounds have also been shown for more general models (e.g. @cite_36 ).
@cite_36
2065240689
Proving lower bounds for range queries has been an active topic of research since the late 70s, but so far nearly all results have been limited to the (rather restrictive) semigroup model. We consider one of the most basic range problem, orthogonal range counting in two dimensions, and show almost optimal bounds in the group model and the (holy grail) cell-probe model. Specifically, we show the following bounds, which were known in the semigroup model, but are major improvements in the more general models:* In the group and cell-probe models, a static data structure of size n lgO(1) n requires Omega(lg n lglg n) time per query. This is an exponential improvement over previous bounds, and matches known upper bounds.* In the group model, a dynamic data structure takes time Omega((lg n lglg n)2) per operation. This is close to the O(lg2 n) upper bound, where as the previous lower bound was Omega(lg n). Proving such (static and dynamic) bounds in the group model has been regarded as an important challenge at least since [Fredman, JACM 1982] and [Chazelle, FOCS 1986].