Introduzione
Gli algoritmi quantistici offrono vantaggi dimostrabili rispetto agli algoritmi classici nel modello di calcolo basato su query. Ma che cosa succede in un modello di calcolo più standard, dove gli input dei problemi vengono forniti esplicitamente anziché sotto forma di oracolo o scatola nera? Si tratta di una domanda molto più difficile a cui rispondere, e per affrontarla dobbiamo prima stabilire una solida base su cui fondare la nostra analisi. Questo è lo scopo principale di questa lezione.
Inizieremo parlando del costo computazionale, sia per i calcoli classici che per quelli quantistici, e di come può essere misurato. Si tratta di un concetto generale che può essere applicato a un'ampia gamma di problemi computazionali — ma per semplicità lo esamineremo principalmente attraverso la lente della teoria computazionale dei numeri, che affronta attività computazionali probabilmente familiari alla maggior parte dei lettori, tra cui l'aritmetica di base, il calcolo del massimo comune divisore e la fattorizzazione intera. Sebbene la teoria computazionale dei numeri sia un dominio applicativo ristretto, questi problemi si prestano bene a illustrare le questioni fondamentali (e risultano anche molto rilevanti per la lezione che segue questa).
La nostra attenzione è rivolta agli algoritmi, non all'hardware sempre più avanzato su cui vengono eseguiti. Di conseguenza, ci interessa maggiormente capire come il costo di esecuzione di un algoritmo scala al crescere della dimensione delle istanze del problema su cui viene eseguito, piuttosto che quanti secondi, minuti o ore richiede un determinato calcolo. Ci concentriamo su questo aspetto del costo computazionale riconoscendo che gli algoritmi hanno un'importanza fondamentale, e che con lo sviluppo della tecnologia verranno naturalmente applicati a istanze di problemi sempre più grandi, su hardware sempre più veloce e affidabile.
Infine, affronteremo un compito di importanza cruciale: eseguire calcoli classici su computer quantistici. Questo compito è importante non perché speriamo di sostituire i computer classici con quelli quantistici — cosa che sembra estremamente improbabile a breve, ammesso che accada mai — ma perché apre molte interessanti possibilità per gli algoritmi quantistici. In particolare, i calcoli classici eseguiti su computer quantistici diventano disponibili come subroutine, sfruttando efficacemente decenni di ricerca e sviluppo sugli algoritmi classici per ottenere vantaggi computazionali quantistici.
Video della lezione
Nel video seguente, John Watrous ti guida attraverso i contenuti di questa lezione sui fondamenti algoritmici quantistici. In alternativa, puoi aprire il video YouTube di questa lezione in una finestra separata. Scarica le slide di questa lezione.