Algoritmul de căutare al lui Grover
Algoritmul de căutare al lui Grover este un algoritm conceput de Lov Grover în 1996 la Bell Labs pentru a rezolva o problemă de căutare într-o bază de date nediferențiată de N elemente în timp O ( N 1/2 ) folosind O (log N ) ca spațiu de memorare. Un exemplu clasic ar putea fi căutarea într-un director telefonic a unui nume având doar numărul de telefon. Dacă aveți un computer clasic, puteți ajunge la nume după ce căutați în medie jumătate din listă. Algoritmul lui Grover, exploatând proprietatea de suprapunere a qubitelor, poate ajunge la răspunsul corect mult mai repede. Algoritmul lui Grover poate fi utilizat în teoria coliziunilor .
Implementare
Nu există nicio mașină cuantică scalabilă care să implementeze versiunea descrisă a algoritmului lui Grover. Versiunile compilate, adică reduse pentru cazuri specifice, au fost deja efectuate: de exemplu într-un registru în stare solidă (embrionul unui circuit integrat) pe un semiconductor hibrid de diamante, obținut de cercetătorii de la Delft Polytechnic, din Olanda, din statul Iowa Universitatea și Universitatea din California din Santa Barbara [1] [2] .
Notă
- ^ T. van der Sar, ZH Wang, MS Blok, H. Bernien, TH Taminiau, DM Toyli, DA Lidar, DD Awschalom, R. Hanson & VV Dobrovitski , Porți cuantice protejate împotriva decoerenței pentru un registru de centrifugare hibrid în stare solidă , în Natură , Nu. 484, 5 aprilie 2012, 84-86. Adus la 10 aprilie 2012 .
- ^ Un computer cuantic în diamant , în Științele 6 aprilie 2012. Adus la 10 aprilie 2012 .
Bibliografie
- Grover LK: Un algoritm mecanic cuantic rapid pentru căutarea bazelor de date , Proceedings, 28th Simposium anual ACM on theory of computing, (mai 1996) p. 212
- Grover LK: De la ecuația lui Schrödinger la algoritmul de căutare cuantică , American Journal of Physics, 69 (7): 769-777, 2001. Revizuirea pedagogică a algoritmului și a istoriei sale.
- Nielsen, MA și Chuang, IL Calcul cuantic și informații cuantice . Cambridge University Press, 2000. Capitolul 6.
- Ce este o agendă telefonică cuantică? , Lov Grover, Lucent Technologies
- Algoritmul lui Grover: Căutare în baza de date cuantică , C. Lavor, LRU Manssur, R. Portugalia
- Algoritmul lui Grover pe arxiv.org , pe xstructure.inr.ac.ru .
Elemente conexe
linkuri externe
- Un computer cuantic în diamant , pe lescienze.it .
