Introduzione

L'algoritmo di Grover è un algoritmo quantistico per i cosiddetti problemi di ricerca non strutturati che offre un miglioramento quadratico rispetto agli algoritmi classici. Ciò significa che l'algoritmo di Grover richiede un numero di operazioni dell'ordine della radice quadrata del numero di operazioni necessarie per risolvere una ricerca non strutturata in modo classico, il che equivale a dire che gli algoritmi classici per la ricerca non strutturata devono avere un costo almeno dell'ordine del quadrato del costo dell'algoritmo di Grover.

L'algoritmo di Grover, insieme alle sue estensioni e alla metodologia sottostante, si rivela ampiamente applicabile, portando a un vantaggio quadratico per molti compiti computazionali interessanti che inizialmente potrebbero non sembrare problemi di ricerca non strutturata in superficie.

Sebbene l'ampia applicabilità della tecnica di ricerca di Grover sia convincente, all'inizio della lezione si deve riconoscere che il vantaggio quadratico che offre sembra improbabile che porti presto a un vantaggio pratico dell'informatica quantistica rispetto a quella classica. L'hardware di calcolo classico è molto più avanzato di quello quantistico e il vantaggio quadratico dei quanti rispetto ai classici offerto dall'algoritmo di Grover sarà sicuramente spazzato via dalle sbalorditive velocità di clock dei moderni computer classici per qualsiasi problema di ricerca non strutturato che possa essere eseguito in tempi brevi.

Con il progredire della tecnologia di calcolo quantistico, tuttavia, l'algoritmo di Grover potrebbe avere un potenziale. Infatti, alcuni degli algoritmi classici più importanti e d'impatto mai scoperti, tra cui la trasformata di Fourier veloce e l'ordinamento veloce (ad esempio, quicksort e merge sort), offrono un vantaggio leggermente inferiore a quello quadratico rispetto agli approcci ingenui ai problemi che risolvono. La differenza fondamentale, naturalmente, è che per eseguire l'algoritmo di Grover è necessaria una tecnologia completamente nuova (ovvero l'informatica quantistica). Sebbene questa tecnologia sia ancora agli albori rispetto all'informatica classica, non dobbiamo sottovalutare il potenziale dei progressi tecnologici che potrebbero consentire un vantaggio quadratico dell'informatica quantistica rispetto a quella classica e offrire un giorno vantaggi pratici tangibili.

Video della lezione

Nel video seguente, John Watrous illustra i contenuti di questa lezione sull'algoritmo di Grover. In alternativa, è possibile aprire il video YouTube per questa lezione in una finestra separata. Scaricate le diapositive di questa lezione.