[Grover96] A fast quantum mechanical algorithm for database search

Authors: Lov K. Grover | Venue: STOC 1996 | Source

Presented the quantum algorithm for unstructured search that finds a marked element among $N$ items in $O(\sqrt{N})$ quantum queries, compared to $\Omega (N)$ classically. This is optimal for quantum query complexity. In cryptographic terms, Grover’s algorithm gives a generic quadratic speedup against symmetric-key primitives, implying that $n$-bit security requires $2n$-bit keys in the post-quantum setting (e.g., AES-256 for 128-bit post-quantum security).

BibTeX

Copy

@Inproceedings{STOC:Grover96,
  author = {Lov K. Grover},
  title = {A Fast Quantum Mechanical Algorithm for Database Search},
  pages = {212--219},
  booktitle = {28th Annual {ACM} Symposium on Theory of Computing},
  address = {Philadephia, PA, USA},
  month = {may~22--24},
  publisher = {{ACM} Press},
  year = {1996},
  doi = {10.1145/237814.237866},
}