HackerPapers

arXiv:quant-ph/9711070quant-ph

Grover's quantum searching algorithm is optimal

Christof Zalka

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

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.

arXiv comments
13 pages, LaTeX, essentially published version
Journal reference
Phys.Rev. A60 (1999) 2746-2751
DOI
doi:10.1103/PhysRevA.60.2746
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Dec 2025 to Dec 2025.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Quantum Error Correction Goes FOOM 1 comment

    • Yes, speed matters. No, quantum computers can't do everything instantly even with unbounded qubits. A well studied example is that it's impossible to parallelize the steps in Grover's algorithm. To find a preimage amongst N possibilities, with only black box access, you need…

      StrilancView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.