Introduzione
L'algoritmo di Grover è un algoritmo quantistico per i cosiddetti problemi di ricerca non strutturata che offre un miglioramento quadratico rispetto agli algoritmi classici. Questo significa che l'algoritmo di Grover richiede un numero di operazioni dell'ordine della radice quadrata del numero di operazioni necessarie per risolvere la 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 interessanti compiti computazionali che in apparenza potrebbero non sembrare problemi di ricerca non strutturata.
Sebbene la vasta applicabilità della tecnica di ricerca di Grover sia convincente, occorre riconoscere fin dall'inizio di questa lezione che il vantaggio quadratico che offre sembra difficilmente in grado di portare a un vantaggio pratico del calcolo quantistico su quello classico nel breve termine. L'hardware per il calcolo classico è molto più avanzato dell'hardware per il calcolo quantistico — e il vantaggio quadratico del quantistico sul classico offerto dall'algoritmo di Grover sarà certamente annullato dalle straordinarie velocità di clock dei moderni computer classici per qualsiasi problema di ricerca non strutturata che potrebbe essere eseguito in tempi ragionevoli.
Con l'avanzare della tecnologia del calcolo quantistico, tuttavia, l'algoritmo di Grover potrebbe avere un grande potenziale. Alcuni degli algoritmi classici più importanti e influenti mai scoperti, tra cui la trasformata di Fourier veloce e l'ordinamento rapido (ad esempio, quicksort e merge sort), offrono un vantaggio leggermente inferiore a quadratico rispetto agli approcci ingenui ai problemi che risolvono. La differenza fondamentale qui, ovviamente, è che per eseguire l'algoritmo di Grover è necessaria una tecnologia del tutto nuova (ovvero il calcolo quantistico). Sebbene questa tecnologia sia ancora agli albori rispetto al calcolo classico, non dobbiamo sottovalutare troppo in fretta il potenziale dei progressi tecnologici che potrebbero un giorno consentire a un vantaggio quadratico del quantistico sul classico di offrire benefici pratici tangibili.
Video della lezione​
Nel video seguente, John Watrous ti guida attraverso i contenuti di questa lezione sull'algoritmo di Grover. In alternativa, puoi aprire il video YouTube di questa lezione in una finestra separata. Scarica le slide di questa lezione.