%0 Journal Article
%T Quantum search for multiple items using parallel queries
%A Lov K. Grover
%A Jaikumar Radhakrishnan
%J Physics
%D 2004
%I arXiv
%X In the quantum database search problem we are required to search for an item in a database. In this paper, we consider a generalization of this problem, where we are provided d identical copes of a database each with N items which we can query in parallel. Then, given k items, we are required to determine the locations where these items are stored. We show that any quantum algorithm for this task must perform Omega(sqrt{Nk/d min{d,k}}) parallel queries. We also design an algorithm whose performance comes within a factor O(log d) of this lower bound.
%U http://arxiv.org/abs/quant-ph/0407217v1