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 discutendo il 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 delle istanze del problema, 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. Il motivo per cui questo compito è importante non è che speriamo di sostituire i computer classici con quelli quantistici — il che sembra estremamente improbabile che accada a breve, se mai accadrà — ma piuttosto 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 nella ricerca di 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.