È difficile rispondere alla domanda della studentessa che sta facendo una ricerca sulla computazione quantistica senza sapere qual è il suo livello di conoscenze di base (in particolare nella fisica quantistica, nell'informatica, nella teoria dei numeri). Proverò quindi a rispondere nell'ipotesi che la signorina sia una studentessa della scuola media superiore, con conoscenze solo qualitative su tutte queste cose.

La proprietà fondamentale dei sistemi fisici quantistici, che li differenzia così profondamente da quelli classici, è il fatto che i loro stati (cioè l'insieme dei valori delle variabili fisiche che li caratterizzano), contrariamente a quanto avviene per quelli classici, possono esistere "in sovrapposizione". Questo, un po' rozzamente, significa che il sistema può stare in più stati simultaneamente (questo fatto è, con una metafora un po' macabra, gergalmente indicato dai fisici come il fenomeno del "gatto di Schroedinger", con riferimento a un esperimento, per fortuna solo ideale, in cui si immagina un complesso marchingegno che — grazie a un fenomeno quantistico casuale, come la emissione di radiazione di un atomo radioattivo — può uccidere un gatto: solo facendo una "misura", vale a dire andando a vedere come sta il gatto, si può decidere se questo sia vivo o morto, mentre fino a che esso è in un contesto quantistico e non viene osservato, il gatto è simultaneamente vivo e morto). In particolare esistono degli stati quantistici di sistemi a molte componenti, ad esempio molte particelle, che costituiscono sovrapposizioni speciali. Sono i cosiddetti stati entangled (la parola, generalmente non tradotta in italiano, significa "intrecciati"), che hanno la proprietà di descrivere situazioni in cui lo stato globale è ben definito, ma non corrisponde a stati ben definiti delle parti che lo compongono. Gli stati entangled sono la risorsa più preziosa per il calcolo quantistico, in quanto coinvolgono tutte le parti costituenti il sistema collettivamente e sono dunque lo strumento più adatto per ottenere quello che è l'obiettivo principale del calcolo quantistico: di esplorare in un solo passo tutto lo spazio delle possibili "risposte" a un dato problema. Se il calcolatore è ben costruito, sarà poi un'altra caratteristica della materia quantistica, la proprietà di avere le stesse caratteristiche di un'onda, a cancellare — per interferenza distruttiva — quegli stati che non danno la risposta corretta al problema in esame, e a esaltare — per interferenza costruttiva — gli stati in cui è stata "codificata" la risposta cercata.

Tutta questa premessa per spiegare alla studentessa come di fatto non ci siano algoritmi quantistici "semplici" (come lei chiede): gli algoritmi quantistici sono allo stesso tempo tutti semplici, in quanto eseguono il loro compito in un solo passo (il calcolo quantistico è intrinsecamente e totalmente "parallelo"), e sono tutti complessi perché la manipolazione della informazione che richiedono è resa complicata in ogni caso proprio perché deve eseguire in un solo passo una molteplicità di trasformazioni. Spesso poi gli algoritmi quantistici sono una ingegnosa mistura dell'uso intelligente e sottile di proprietà del sistema nella sua descrizione data dalla meccanica quantistica, e di proprietà matematiche del problema in esame. Per esempio, il famoso algoritmo di Shor (che esegue in un tempo breve — cioè che cresce con la lunghezza dell'input espressa in bit solo come una potenza — un calcolo, la fattorizzazione di un numero intero nei suoi fattori primi, che con algoritmi classici si sa richiedere un tempo che cresce invece esponenzialmente con la lunghezza dell'input). La proprietà fondamentale di teoria dei numeri su cui l'algoritmo di Shor si basa è il fatto che trovare fattori primi di un numero dato è equivalente a trovare il periodo di una funzione periodica. Le mostro questo con un paio di esempi.

Supponga di voler fattorizzare il numero N   =   15 e immagini di procedere così: innanzi tutto scelga ("tira a sorte") un numero ausiliario x (per esempio immaginiamo di aver trovato x = 2); poi consideri l'insieme di tutti i numeri interi n : n= 0 1 2 3 4 5  6 7 ..... e calcoli l'insieme associato dei numeri x elevato a n : 1 2 4 8  16 32 64 128 .... ; infine calcoli di questi numeri il resto "modulo N" (cioè quanto rimane togliendo da essi il più grande multiplo di N possibile): con N   =   15 la sequenza che rimane sarà 1 2 4 8 1 2 4 8 ... Si vede facilmente che questa sequenza è periodica; un insieme di r   =   4 numeri (1 2 4 8) è ripetuto periodicamente infinite volte. Bene: un vecchissimo teorema di teoria dei numeri dice che i due numeri che si ottengono sommando e sottraendo 1 dalla potenza r/2 di x hanno un fattore primo in comune con N. Nell'esempio in esame r/2 = 2, il quadrato di x è uguale a 4 e i due numeri sono 3 e 5. L'esempio è molto semplice e un po' costruito ad hoc (i due numeri sono proprio i due fattori di N   =   3 per 5), ma il teorema ha validità del tutto generale. Può per esercizio provarsi a studiare un altro caso: ad esempio N   =   119 (= 7 per 17), x=3, in cui troverebbe r=4 e i due numeri 170 e 160, il primo dei quali è uguale a 17 per 10 e il secondo a 24 per 7. La potenza dell'algoritmo di Shor nasce dal fatto che trovare i fattori primi comuni tra due numeri interi è un algoritmo (già noto a Euclide) che costa solo un numero di passi polinomiale nella lunghezza dell'input, ed è quindi molto efficiente; e che - proprio per le sue proprietà ondulatorie - con un sistema quantistico è facile analizzare una funzione periodica e valutarne il periodo.

Per quanto riguarda la domanda di referenze bibliografiche, ripeto che dovrei avere più informazione su quanto la studentessa sia in grado di addentrarsi nelle (intricate) questioni tecniche. Sempre immaginando che non ne sappia troppo, le indicherei due cose scritte da me (non per farmi pubblicità, né per presunzione, ma semplicemente perché mi risulta che siano le sole cose di livello divulgativo medio/alto disponibili in italiano: la prima, più accessibile perché priva del tutto di formule, è un mio articolo su "Le Scienze" (corredato anche di alcune referenze) la seconda, un po' più tecnica e adatta solo se la signorina conosce un po' di meccanica quantistica e degli strumenti matematici che le sono propri, è un mio recente articolo su "Bollettino dell'Unione Matematica Italiana".

1) M. Rasetti, Dal bit al qu-bit: per sfidare la complessità Le Scienze, N. 385 (settembre 2000) pag. 82-88

2) M. Rasetti, "Il calcolo quantistico: una sfida per la matematica del 2000", Bollettino dell'Unione Matematica Italiana (8) 3-A (agosto 2000) pagg. 201-222