Come la fisica quantistica porta a decifrare algoritmi comuni

I l'ascesa dell'informatica quantistica e il suo tool proprietario implicazioni per gli attuali standard di crittografia sono ben noti. Ma perché esattamente i computer quantistici dovrebbero essere particolarmente abili nel violare la crittografia? La risposta è un bel po' di giocoleria matematica chiamata L'algoritmo di Shor. La domanda che rimane è: cosa fa questo algoritmo che fa sì che i computer quantistici siano molto più bravi a decifrare la crittografia? In questo video, YouTuber fisica dei minuti lo spiega nel suo tradizionale stile da cartone animato sulla lavagna.

"Il calcolo quantistico ha il potenziale per rendere super, super facile l'accesso ai dati crittografati, come avere una spada laser che puoi usare per tagliare qualsiasi serratura o barriera, non importa quanto sia forte", afferma minutephysics. "L'algoritmo di Shor è quella spada laser."

Secondo il video, l'algoritmo di Shor si basa sulla comprensione che per qualsiasi coppia di numeri, alla fine moltiplicando uno di essi per sé si raggiungerà un fattore dell'altro numero più o meno 1. Quindi indovina il primo numero e lo fattorizza fuori, sommando e sottraendo 1, fino ad arrivare al secondo numero. Ciò sbloccherebbe la crittografia (in particolare RSA qui, ma funziona alcuni altri tipi) perché allora avremmo entrambi i fattori.

Uno dei motivi per cui questo processo apparentemente semplice si basa sullo sviluppo di potenti computer quantistici è che trovare la potenza corretta per moltiplicare il primo numero per trovare un fattore del secondo numero (N) ± 1 richiede un'enorme quantità di tentativi. La chiave di crittografia è un numero piuttosto lungo e quindi la potenza potrebbe variare da 1 a milioni. Ma la forza bruta non è il motivo per cui i computer quantistici funzionano così bene qui.

I superpoteri delle sovrapposizioni

In breve, grazie alla sovrapposizione quantistica, un computer quantistico può calcolare molte risposte per un singolo input. Tuttavia, il video dice che ottieni solo un output di risposta alla volta, con le probabilità allegate. Per risolvere questo problema, il calcolo è impostato in modo che le risposte sbagliate interferiscano tra loro in modo che sia probabile che venga emessa solo la risposta corretta (o almeno una buona ipotesi). Quel calcolo, che si concentra sulla ricerca della giusta potenza p, è l'algoritmo di Shor.

È tutto estremamente matematico, con un assist di L'algoritmo di Euclide, così come una trasformata quantistica di Fourier che trasforma una serie di sovrapposizioni di sovrapposizioni in onde sinusoidali che interferiscono in modo costruttivo (aggiungendo l'una all'altra) o in modo distruttivo, ovvero si annullano a vicenda. Il video dice che, essenzialmente, puoi truccarlo in modo che solo 1/p viene salvato, con tutte le altre risposte interferite in modo distruttivo fuori dalla contesa. Una volta che sei lì, è una passeggiata nel parco da trovare p, il che rende molto più semplice trovare i due fattori di crittografia. Guarda l'intero video per maggiori dettagli e forse per sentirti un po' più intelligente.

A proposito, Peter Shor lo è ancora fiorente, e se sei interessato a un'analisi approfondita di come ha rotto Internet, ecco un altro video in cui l'uomo stesso spiega come ha capito il suo omonimo capolavoro.