nLab Grover's algorithm

Idea

A search algorithm for quantum computers (cf. quantum algorithm) which is expected to produce quadratic speedup (from $O(N)$ to $O(\sqrt{N})$) compared to classical computers.

Related concepts

• Shor's algorithm

• Deutsch-Jozsa algorithm

• quantum complexity theory

• quantum supremacy

References

Due to:

• Lov K. Grover, A fast quantum mechanical algorithm for database search, STOC ‘96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (1996) 212-219 [arXiv:quant-ph/9605043, doi:10.1145/237814.237866]

Survey:

• Renato Portugal, Basic Quantum Algorithms [arXiv:2201.10574]

Lecture notes:

• Scott Aaronson, Chapters 22-24 of: Introduction to Quantum Information Science (2018) [pdf, webpage]

Realization in experiment with error detecting codes realizing quantum advantage:

• Bibek Pokharel, Daniel Lidar, Better-than-classical Grover search via quantum error detection and suppression [arXiv:2211.04543]

Implementation in Quipper:

• Safat Siddiqui, Mohammed Jahirul Islam, Omar Shehab, §4.4 in: Five Quantum Algorithms Using Quipper [arXiv:1406.4481]

See also

• Wikipedia, Grover’s algorithm

Discussion in terms of quantum information theory via dagger-compact categories:

• Jamie Vicary, Section 3 of: The Topology of Quantum Algorithms, (LICS 2013) Proceedings of 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 93-102 (arXiv:1209.3917)

Review in:

• Ali Nabi Duman, The Topology of Grover Algorithm (arXiv:1405.4425)

• Kamil Khadiev, §§5-9 in: Lecture Notes on Quantum Algorithms [arXiv:2212.14205]