Introduzione

In questa prima lezione del corso, formuleremo un semplice framework algoritmico — noto come modello a query — ed esploreremo i vantaggi che i computer quantistici offrono all'interno di questo framework.

Il modello di calcolo a query è come una capsula di Petri per le idee algoritmiche quantistiche. È rigido e artificioso nel senso che non rappresenta accuratamente il tipo di problemi computazionali di cui generalmente ci occupiamo nella pratica, ma si è comunque rivelato incredibilmente utile come strumento per sviluppare tecniche algoritmiche quantistiche. Tra queste ci sono quelle alla base degli algoritmi quantistici più noti, come l'algoritmo di Shor per la fattorizzazione degli interi. Il modello a query è anche un framework molto utile per spiegare le tecniche algoritmiche quantistiche.

Dopo aver introdotto il modello a query, discuteremo il primissimo algoritmo quantistico mai scoperto, ovvero l'algoritmo di Deutsch, insieme a un'estensione dell'algoritmo di Deutsch nota come algoritmo di Deutsch-Jozsa. Questi algoritmi dimostrano vantaggi quantificabili dei computer quantistici rispetto a quelli classici nel contesto del modello a query. Discuteremo poi un algoritmo quantistico noto come algoritmo di Simon, che offre un vantaggio più solido e soddisfacente dei computer quantistici rispetto a quelli classici, per ragioni che verranno spiegate quando ci arriveremo.

Video della lezione

Nel video seguente, John Watrous ti accompagna attraverso i contenuti di questa lezione sugli algoritmi quantistici a query. In alternativa, puoi aprire il video YouTube di questa lezione in una finestra separata. Scarica le slide di questa lezione.