FONDAMENTI E PRINCIPI DI ELABORAZIONE QUANTISTICA, SPIEGATI QUASI FACILI: il problema di simon o della complessita’ del calcolo

Il Problema di Simon è un problema di computazione quantistica che dimostra come un algoritmo quantistico possa essere più veloce e più efficiente di un algoritmo classico. Il problema consiste nel trovare una stringa segreta s data una funzione nascosta f che soddisfa la proprietà f(x) = f(x ⊕ s) per ogni stringa x di lunghezza n, dove ⊕ è l’operazione di XOR bit a bit. In altre parole, la funzione f è periodica con periodo s.

Un algoritmo classico probabilistico (o deterministico) deve interrogare la funzione f un numero esponenziale di volte per trovare s con alta probabilità. Invece, un algoritmo quantistico può trovare s con un numero lineare di interrogazioni, sfruttando il fenomeno dell’interferenza quantistica. L’algoritmo quantistico di Simon è il seguente:

1. Preparare due registri quantistici di n qubit ciascuno nello stato |00…0⟩.
2. Applicare la trasformata di Hadamard a ogni qubit del primo registro, ottenendo lo stato (1/√2^n) ∑_x |x⟩|0⟩, dove la somma è su tutte le stringhe x di lunghezza n.
3. Applicare la funzione f al primo registro usando una porta quantistica U_f che mappa lo stato |x⟩|y⟩ in |x⟩|y ⊕ f(x)⟩, ottenendo lo stato (1/√2^n) ∑_x |x⟩|f(x)⟩.
4. Misurare il secondo registro e ottenere un valore y = f(x) per qualche x. Questo non cambia il primo registro, che rimane nello stato (1/√2^n) ∑_{x: f(x)=y} |x⟩.
5. Applicare nuovamente la trasformata di Hadamard a ogni qubit del primo registro, ottenendo lo stato (1/2^n) ∑z (∑{x: f(x)=y} (-1)^{x⋅z}) |z⟩, dove x⋅z è il prodotto scalare modulo 2 tra x e z.
6. Misurare il primo registro e ottenere un valore z tale che z⋅s = 0 con alta probabilità. Questo significa che z è ortogonale a s nello spazio vettoriale {0,1}^n.

Ripetendo questo algoritmo per n volte, si ottengono n valori linearmente indipendenti z_i tali che z_i⋅s = 0. Risolvendo questo sistema lineare di equazioni modulo 2, si può trovare s.

Questo algoritmo mostra come la computazione quantistica possa offrire un vantaggio esponenziale rispetto alla computazione classica per alcuni problemi specifici. Tuttavia, il Problema di Simon non ha molte applicazioni pratiche e serve principalmente come esempio didattico e come base per altri algoritmi quantistici più utili, come l’algoritmo di Shor per la fattorizzazione di numeri interi.