2004/07/27 by Lov K. Grover, Grover, Lov K., Jaikumar Radhakrishnan +1 · 1 citation
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0407217
Six pages; no figures, LaTeX
arxiv created 2004/07/27 · arxiv updated 2009/12/01
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(sqrtNk/d mind,k) parallel queries. We also design an algorithm whose performance comes within a factor O(log d) of this lower bound.