Algoritmo di ricerca di Grover

L'algoritmo di ricerca di Grover è un algoritmo ideato da Lov Grover nel 1996 ai Bell Labs per risolvere un problema di ricerca in un database indifferenziato di N elementi in O(N^1/2) tempo usando O(log N) come spazio di memorizzazione. Un classico esempio può essere la ricerca in un elenco telefonico di un nome disponendo solo del numero telefonico. Disponendo di un computer classico si può pervenire al nome dopo aver cercato mediamente metà dell'elenco. L'algoritmo di Grover, sfruttando la proprietà di sovrapposizione dei qubit, può pervenire alla risposta corretta molto più velocemente. L'algoritmo di Grover può essere utilizzato nella Teoria delle collisioni.

Implementazione

Non esiste una macchina quantistica scalabile che implementi la versione descritta dell'algoritmo di Grover. Versioni compilate, ossia ridotte per casi specifici, sono invece già state eseguite: ad esempio in un registro allo stato solido (l'embrione di un circuito integrato) su semiconduttore ibrido al diamante, ottenuto dai ricercatori del Politecnico di Delft, nei Paesi Bassi, della Iowa State University e dell'Università della California a Santa Barbara^[1]^[2].

Note

^ T. van der Sar, Z. H. Wang, M. S. Blok, H. Bernien, T. H. Taminiau, D. M. Toyli, D. A. Lidar, D. D. Awschalom, R. Hanson & V. V. Dobrovitski, Decoherence-protected quantum gates for a hybrid solid-state spin register, in Nature, n. 484, 5 aprile 2012, 84-86. URL consultato il 10 aprile 2012.
^ Un computer quantistico nel diamante, in Le Scienze, 6 aprile 2012. URL consultato il 10 aprile 2012.

Bibliografia

Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001. Pedagogical review of the algorithm and its history.
Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
What's a Quantum Phone Book?, Lov Grover, Lucent Technologies
Grover's Algorithm: Quantum Database Search, C. Lavor, L.R.U. Manssur, R. Portugal
Grover's algorithm on arxiv.org, su xstructure.inr.ac.ru.

Voci correlate

Collegamenti esterni

Un computer quantistico nel diamante, su lescienze.it.

Portale Fisica

Portale Informatica

[nature-1] T. van der Sar, Z. H. Wang, M. S. Blok, H. Bernien, T. H. Taminiau, D. M. Toyli, D. A. Lidar, D. D. Awschalom, R. Hanson & V. V. Dobrovitski, Decoherence-protected quantum gates for a hybrid solid-state spin register, in Nature, n. 484, 5 aprile 2012, 84-86. URL consultato il 10 aprile 2012.

[lescienze-2] Un computer quantistico nel diamante, in Le Scienze, 6 aprile 2012. URL consultato il 10 aprile 2012.

[1]

[2]