Lov Grover

Informatico e fisico — Lov Kumar Grover (nato in India nel 1961) è un informatico e fisico indiano-statunitense, noto per i suoi contributi all’informatica quantistica. Formatosi all’Indian Institute of Technology di Delhi e alla Stanford University, ha lavorato a lungo ai Bell Laboratories. Nel 1996 ideò l’algoritmo di ricerca quantistica che porta il suo nome, uno dei risultati fondamentali del calcolo quantistico. L’algoritmo di Grover consente di cercare un elemento in un database non ordinato di N elementi con circa la radice quadrata di N operazioni, offrendo un’accelerazione quadratica rispetto a qualunque algoritmo classico. Insieme all’algoritmo di Shor, è considerato una delle dimostrazioni chiave del potenziale vantaggio dei computer quantistici.

Curiosità

A differenza dell’accelerazione esponenziale di Shor, il vantaggio ‘quadratico’ di Grover è dimostrabilmente ottimale: nessun algoritmo quantistico può cercare in un database non ordinato più velocemente.

Teorie e contributi

• Algoritmo di Grover — Ricerca quantistica in un insieme non ordinato di $N$ elementi in circa $O(\sqrt{N})$ passi, contro gli $O(N)$ classici.

Presente nei capitoli

21

Atomi collegati

1 atomi collegati.

21 Introduzione alla meccanica quantistica

• La disuguaglianza di Bell

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