  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.
