Showing changes from revision #9 to #10: Added | Removed | Changed

Contents

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](https://arxiv.org/abs/quant-ph/9605043), doi:10.1145/237814.237866]

Survey:

• Renato Portugal, Basic Quantum Algorithms [[arXiv:2201.10574](https://arxiv.org/abs/2201.10574)]

Lecture notes:

• Scott Aaronson, Chapters 22-24 of: Introduction to Quantum Information Science (2018) [[pdf](https://www.scottaaronson.com/qclec.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](https://arxiv.org/abs/2211.04543)]

Implementation in Quipper:

• Safat Siddiqui, Mohammed Jahirul Islam, Omar Shehab, §4.4 in: Five Quantum Algorithms Using Quipper [[arXiv:1406.4481](https://arxiv.org/abs/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, Science pages (2013) 93-102 ( [[arXiv:1209.3917](https://arxiv.org/abs/1209.3917)]arXiv:1209.3917)

Review in:

• Ali Nabi Duman, The Topology of Grover Algorithm ( [[arXiv:1405.4425](https://arxiv.org/abs/1405.4425)]arXiv:1405.4425)

• Kamil Khadiev, §§5-9 in: Lecture Notes on Quantum Algorithms [[arXiv:2212.14205](https://arxiv.org/abs/2212.14205)]