[Zal97] Grover’s quantum searching algorithm is optimal

Authors: Christof Zalka | Venue: arXiv | Source

Abstract

I improve the tight bound on quantum searching by Boyer et al. (quant-ph/9605034) 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.

BibTeX

Copy

@article{Zal97,
  author  = {Christof Zalka},
  title   = {Grover's Quantum Searching Algorithm Is Optimal},
  journal = {Physical Review A},
  volume  = {60},
  number  = {4},
  pages   = {2746--2751},
  year    = {1999},
  url     = {https://arxiv.org/abs/quant-ph/9711070}
}