Lov Grover

Computer scientist and physicist — Lov Kumar Grover (born in India in 1961) is an Indian-American computer scientist and physicist, known for his contributions to quantum computing. Trained at the Indian Institute of Technology, Delhi, and at Stanford University, he worked for many years at Bell Laboratories. In 1996 he devised the quantum search algorithm that bears his name, one of the fundamental results of quantum computing. Grover’s algorithm allows an element to be found in an unsorted database of N elements in about the square root of N operations, offering a quadratic speed-up over any classical algorithm. Alongside Shor’s algorithm, it is considered one of the key demonstrations of the potential advantage of quantum computers.

Trivia

Unlike Shor’s exponential speed-up, Grover’s ‘quadratic’ advantage is provably optimal: no quantum algorithm can search an unsorted database any faster.

Theories and contributions

• Grover’s algorithm — Quantum search over an unsorted set of $N$ elements in about $O(\sqrt{N})$ steps, versus the classical $O(N)$.

Featured in chapters

21

Linked atoms

1 linked atoms.

21 Introduzione alla meccanica quantistica

• Bell’s inequality