Introduzione

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

Il modello di query della computazione è come una piastra di Petri per le idee algoritmiche quantistiche. È rigido e innaturale, nel senso che non rappresenta accuratamente i tipi di problemi computazionali che generalmente ci interessano nella pratica, ma si è comunque dimostrato incredibilmente utile come strumento per lo sviluppo di tecniche algoritmiche quantistiche. Tra questi vi sono quelli che alimentano gli algoritmi quantistici più noti, come l'algoritmo di Shor per la fattorizzazione dei numeri interi. Il modello di query è anche un quadro molto utile per spiegare le tecniche algoritmiche quantistiche.

Dopo aver introdotto il modello di query, discuteremo il primo algoritmo quantistico scoperto, l' algoritmo di Deutsch, e una sua estensione nota come algoritmo di Deutsch-Jozsa. Questi algoritmi dimostrano vantaggi quantificabili dei computer quantistici rispetto a quelli classici nel contesto del modello di interrogazione. Discuteremo poi un algoritmo quantistico noto come algoritmo di Simon, che offre un vantaggio più robusto e soddisfacente dei calcoli quantistici rispetto a quelli classici, per ragioni che saranno spiegate quando arriveremo a questo punto.

Video della lezione

Nel video seguente, John Watrous illustra i contenuti di questa lezione sugli algoritmi di query quantistica. In alternativa, è possibile aprire il video YouTube per questa lezione in una finestra separata. Scaricate le diapositive di questa lezione.