Grover's quantum searching algorithm is optimal Export

@misc{citeulike:1375371, abstract = {I improve the tight bound on quantum searching by Boyer et al. (<a href="/abs/quant-ph/9605034">quant-ph/9605034</a>) to a matching bound, thus showing that for any probability of success Grovers quantum searching algorithm is optimal. E.g. for near certain success we have to query the oracle pi/4 sqrt{N} times, where N is the size of the search space. I also show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers. Earlier results left open the possibility of a more efficient parallelization.}, archivePrefix = {arXiv}, author = {Zalka, Christof}, citeulike-article-id = {1375371}, citeulike-linkout-0 = {http://arxiv.org/abs/quant-ph/9711070}, citeulike-linkout-1 = {http://arxiv.org/pdf/quant-ph/9711070}, day = {2}, eprint = {quant-ph/9711070}, keywords = {algorithms, complexity, quantum}, month = {Dec}, posted-at = {2007-06-10 05:58:07}, priority = {5}, title = {Grover's quantum searching algorithm is optimal}, url = {http://arxiv.org/abs/quant-ph/9711070}, year = {1999} }

TY - ELEC ID - citeulike:1375371 L3 - citeulike-article-id:1375371 N2 - I improve the tight bound on quantum searching by Boyer et al. (<a href="/abs/quant-ph/9605034">quant-ph/9605034</a>) to a matching bound, thus showing that for any probability of success Grovers quantum searching algorithm is optimal. E.g. for near certain success we have to query the oracle pi/4 sqrt{N} times, where N is the size of the search space. I also show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers. Earlier results left open the possibility of a more efficient parallelization. TI - Grover's quantum searching algorithm is optimal KW - algorithms KW - complexity KW - quantum AU - Zalka, Christof PY - 1999/Dec/02/ UR - http://arxiv.org/abs/quant-ph/9711070 ER -