Eviterò di parlare dell'algoritmo di Shor e lascerò che tu lo legga da solo: l'algoritmo di Shor è l'algoritmo quantistico ed è il motivo per cui il calcolo quantistico è diventato un argomento così caldo, e non è solo una lettura obbligata, ma Scott Aaronson ha fornito un'introduzione migliore di quella che potrei mai gestire, http://www.scottaaronson.com/blog/?p=208

Invece, ti guiderò attraverso l'algoritmo di Deutsch, che risolve un problema incredibilmente inutile in modo esponenzialmente più veloce di qualsiasi algoritmo classico:

Immagina di avere una funzione $ f $ su una configurazione di $ n $ bit, $ C = \ {0,1 \} ^ n $ che porta ogni configurazione a un singolo bit. Ti prometto in anticipo che questa funzione è:

1. Costante: tutte le configurazioni sono mappate sullo stesso valore.
2. Bilanciata: esattamente metà delle configurazioni mappata a $ 1 $, l'altra metà a $ 0 $.

In modo classico, nel caso peggiore devi valutare la funzione per $ 2 ^ {n-1} + 1 $ configurazioni ( $ O (2 ^ n) $) per verificare in quale categoria rientra $ f $.

Ora, un computer quantistico non è solo un processore parallelo, dove puoi dargli una sovrapposizione delle configurazioni e ottenere $ f $ valutato su tutte. Alla fine della giornata, devi effettuare una misurazione che distrugga la nostra sovrapposizione accuratamente creata, quindi dobbiamo essere intelligenti! La caratteristica fondamentale di un algoritmo quantistico è che usiamo operazioni unitarie per trasformare il nostro stato e usiamo interferenza tra stati in modo che quando misuriamo lo stato alla fine, ci dice qualcosa di non ambiguo.

Quindi, senza ulteriori indugi, l'algoritmo Deutsch per $ n = 2 $ qubit (puoi farlo per molti più qubit, ovviamente, ma volevi un semplice esempio). La "versione quantistica" della nostra funzione è un'operazione unitaria (una "porta quantistica") che mi porta da $ | a \ rangle | b \ rangle $ a $ | a \ rangle | b + f (a) \ rangle $ ( dove l'addizione è modulo 2). Inoltre a mia disposizione c'è un gate che prende ogni singolo bit e lo mette in una particolare sovrapposizione:

$$ | 1 \ rangle \ rightarrow (| 0 \ rangle- | 1 \ rangle) / \ sqrt { 2} $$

$$ | 0 \ rangle \ rightarrow (| 0 \ rangle + | 1 \ rangle) / \ sqrt {2} $$

Il primo passo nell'algoritmo è preparare i miei due qubit come $ | 0 \ rangle | 1 \ rangle $ e quindi applicare questa trasformazione, dandomi lo stato $ (| 0 \ rangle + | 1 \ rangle) (| 0 \ rangle- | 1 \ rangle) / 2 $. Ora valuto la funzione applicando il gate descritto in precedenza, portando il mio stato a

$$ [| 0 \ rangle (| 0 + f (0) \ rangle- | 1 + f (0) \ rangle) + | 1 \ rangle (| 0 + f (1) \ rangle- | 1 + f (1) \ rangle)] / 2 $$

Se lo fissiamo attentamente e pensiamo mod aritmetica 2, vediamo che se $ f (0) = 1 $ il primo termine prende un segno meno relativo al suo stato precedente, e se $ f (0) = 0 $ non accade nulla. Quindi possiamo riscrivere lo stato come

$$ [(- 1) ^ {f (0)} | 0 \ rangle (| 0 \ rangle- | 1 \ rangle) + (- 1) ^ { f (1)} | 1 \ rangle (| 0 \ rangle- | 1 \ rangle)] / 2 $$

o raggruppamento

$$ (| 0 \ rangle + (- 1) ^ {f (0) + f (1)} | 1 \ rangle) (| 0 \ rangle- | 1 \ rangle) / 2 $$

Ora eliminiamo il secondo qubit (non non ne ho più bisogno, e non è impigliato con il primo bit), e applica la seconda trasformazione che ho elencato ancora una volta (e raggruppando, l'algebra è semplice ma noiosa) - alla fine, il nostro stato finale è

$$ [(1 + (- 1) ^ {f (0) + f (1)}) | 0 \ rangle + ((1 - (- 1) ^ {f (0) + f (1)}) | 1 \ rangle] / 2 $$

Infine, misuriamo! Dovrebbe essere chiaro dallo stato precedente che abbiamo risolto il problema ... Se $ f $ è costante, $ f (0) = f (1) $ e misureremo sempre $ | 0 \ rangle $, e se $ f $ è bilanciato allora $ f (0) \ neq f (1) $ e misuriamo sempre $ | 1 \ rangle $.

Alcuni commenti finali: si spera che questo ti dia un po 'di gusto per la struttura di un algoritmo quantistico, anche se sembra una cosa inutile - Consiglio vivamente di andare a leggere l'articolo che ho linkato all'inizio di questa risposta .

Ok, dato che wsc ti ha dato una spiegazione dell'algoritmo di Deutsch, lascia che ti spieghi un altro algoritmo e più utile: l'algoritmo di ricerca di Grover. Questo è un algoritmo di ricerca per un database non ordinato, o per cercare in una scatola nera l'input che si traduce in un output specifico (una primitiva molto utile negli algoritmi). Per un insieme di voci $ N $, supponendo che ci sia solo una voce che soddisfa la query di ricerca, l'algoritmo accetta solo $ O (\ sqrt {N}) $ query, mentre il miglior algoritmo classico possibile accetta $ O (N) $ query del database. Inoltre, l'algoritmo di Grover (con una piccola modifica non entrerò qui) è dimostrabilmente ottimale. Allora, come funziona?

Supponiamo che ci sia un database di $ 2 ^ n $ voci. Per prima cosa prepariamo una sovrapposizione di $ 2 ^ n $ stati classici con fase positiva: $ \ mid S \ rangle = 2 ^ {- \ frac {n} {2}} \ sum_ {x = 1} ^ {2 ^ n} | x \ rangle $. Questo può essere fatto semplicemente applicando una singola porta quantistica (in questo caso una porta Hadamard) a ciascuno di $ n $ qubit inizialmente preparati nello stato zero. Rappresento gli stati incontrati da un diagramma, dove la lunghezza di ogni linea rappresenta la sua ampiezza nella sovrapposizione e se è la direzione dalla linea centrale per indicare la sua fase (in questo caso sarà sempre positiva o negativa) . Lo stato che otteniamo dopo questo passaggio di inizializzazione viene quindi rappresentato come di seguito.

L'algoritmo stesso è costituito da $ r $ round che consistono ciascuno di due passaggi:

1. La fase di uno stato classico nella sovrapposizione viene capovolta se (e solo se) la voce nel database in quella posizione corrisponde alla query di ricerca, come illustrato di seguito. Qui assumiamo che la voce $ m $ sia la voce che corrisponde alla query di ricerca. Si noti che questa è solo una singola query al database, che ha effetti diversi in ogni ramo della funzione d'onda. Ciò si ottiene applicando un operatore $ U_m = I - 2 | m \ rangle \ langle m | $

2. Viene applicato l'operatore "inversione rispetto alla media". Questo è semplicemente un operatore unitario dato da $ U_S = 2 | S \ rangle \ langle S | - I $, dove come prima $ | S \ rangle = 2 ^ {- \ frac {n} {2}} \ sum_ {x = 1} ^ {2 ^ n} | x \ rangle $. L'effetto di questo operatore è molto semplice: l'ampiezza $ A_i $ di ciascuna voce $ i $ viene portata a $ 2 \ mu - A_i $, dove $ mu $ è l'ampiezza media. Ciò equivale a invertire la distanza sopra o sotto la media. Il primo diagramma sotto mostra dove si trova ora la media, mentre il secondo mostra l'effetto dell'applicazione di questo operatore.

Chiaramente l'effetto di questa operazione è di amplificare l'ampiezza della voce corrispondente alla query di ricerca, e ciò continuerà fino a quando la media non si trova al di sotto della linea dello zero (dopo $ r $ round). Ciò si verifica dopo le query $ O (\ sqrt {N}) $. Per vedere questo, notiamo prima che lo stato del sistema dopo ogni round $ i $ può sempre essere scritto nella forma $ | \ psi_i \ rangle = \ cos \ theta_i | s \ rangle + \ sin \ theta_i | m \ mid $, dove $ | s \ rangle = (2 ^ n - 1) ^ {- \ frac {1} {2}} \ sum_ {x \ neq m} | x \ rangle $. Chiaramente $ | s \ rangle $ e $ | m \ rangle $ sono ortogonali, quindi possiamo rappresentare qualsiasi stato incontrato come vettore unitario nel piano 2D attraversato da $ | s \ rangle $ e $ | m \ rangle $.

Consideriamo l'effetto di un singolo round. Prima viene applicato $ U_m $, quindi viene applicato $ U_S $. Nota che $ U_S = 2 | S \ rangle \ langle S | - I = (\ frac {2 (2 ^ n - 1)} {2 ^ n} -1) | s \ rangle \ langle s | + \ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n} | s \ rangle \ langle m | + \ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n} | m \ rangle \ langle s | + (\ frac {2} {2 ^ n} - 1) | m \ rangle \ langle m | $. Quando lo moltiplichiamo per $ U_m $ per ottenere l'operazione totale applicata in un round $ U_S U_m = (\ frac {2 (2 ^ n - 1)} {2 ^ n} -1) | s \ rangle \ langle s | - \ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n} | s \ rangle \ langle m | + \ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n} | m \ rangle \ langle s | + (\ frac {2 (2 ^ n - 1)} {2 ^ n}) | m \ rangle \ langle m | $. Questa è semplicemente una rotazione attraverso un angolo costante $ \ phi = \ sin ^ {- 1} (\ frac {2 \ sqrt {2 ^ n - 1}} {2 ^ n}) \ approx \ frac {2} {\ sqrt {2 ^ n}} $ per $ n $ grandi. Poiché inizialmente iniziamo molto vicino allo stato $ | s \ rangle $, quindi abbiamo bisogno di $ r \ approx \ frac {2} {\ sqrt {2 ^ n}} $, il che significa che otteniamo l'ampiezza massima per $ | m \ rangle $ solo in ~ $ 2 \ sqrt {N} $ query del database.

È facile vedere che questo è impossibile in modo classico, poiché se fai $ m $ query al database, ci sono ancora $ Nm $ voci che non sono state verificate che potrebbero corrispondere al termine di ricerca, il che significa che è necessario controllare un numero lineare di voci per assicurare anche una probabilità costante di trovare la voce corretta.

Spero che questo è utile