La casualità pura e verificabile è difficile da trovare. Due proposte mostrano come trasformare i computer quantistici in fabbriche di casualità.
Pronunciate le parole "supremazia quantistica" in una riunione di scienziati informatici, e probabilmente gli occhi rotoleranno. La frase si riferisce all'idea che i computer quantistici supereranno presto una soglia in cui si esibiranno con compiti relativamente facili che sono estremamente difficili per i computer classici. Fino a poco tempo fa, si pensava che questi compiti avessero un uso limitato nel mondo reale, da cui gli sguardi degli occhi.
Ma ora che si dice che il processore quantistico di Google sia vicino a raggiungere questo obiettivo, l'imminente supremazia quantistica potrebbe rivelarsi avere un'applicazione importante dopo tutto: generare pura casualità.
La casualità è cruciale per quasi tutto ciò che facciamo con la nostra infrastruttura computazionale e di comunicazione. In particolare, viene utilizzato per crittografare i dati, proteggendo qualsiasi cosa, da conversazioni banali a transazioni finanziarie a segreti di stato.
Una casualità genuina e verificabile - pensate che sia la proprietà posseduta da una sequenza di numeri che rende impossibile prevedere il prossimo numero nella sequenza - è estremamente difficile da ottenere.
Ciò potrebbe cambiare quando i computer quantistici dimostrano la loro superiorità. Quei primi compiti, inizialmente intesi semplicemente a mostrare le abilità della tecnologia, potrebbero anche produrre casualità autentica e certificata. "Siamo davvero entusiasti", ha detto John Martinis, un fisico dell'Università della California, Santa Barbara, a capo degli sforzi di Google per l'elaborazione quantica. "Speriamo che questa sia la prima applicazione di un computer quantistico".
Casualità e entropia
La casualità e la teoria dei quanti vanno insieme come un tuono e un lampo. In entrambi i casi, il primo è una conseguenza inevitabile di quest'ultimo. Nel mondo dei quanti, si dice spesso che i sistemi siano in una combinazione di stati - in una cosiddetta "sovrapposizione". Quando si misura il sistema, esso "collassa" in uno solo di questi stati. E mentre la teoria dei quanti ti consente di calcolare le probabilità per ciò che troverai quando fai la tua misurazione, il risultato particolare è sempre fondamentalmente casuale.
I fisici hanno sfruttato questa connessione per creare generatori di numeri casuali. Tutto ciò si basa su misurazioni di una sorta di sovrapposizione quantistica. E mentre questi sistemi sono più che sufficienti per le esigenze di casualità della maggior parte delle persone, possono essere difficili da lavorare. Inoltre, è estremamente difficile dimostrare a uno scettico che questi generatori di numeri casuali sono davvero casuali. Infine, alcuni dei metodi più efficaci per generare casualità verificabili richiedono configurazioni complicate con più dispositivi separati da grandi distanze.
 | |
| Il laboratorio Google AI ha introdotto un processore quantistico a 72-qubit chiamato Bristlecone nel 2018. |
Una recente proposta su come estrarre la casualità da un singolo dispositivo - un computer quantistico - sfrutta un cosiddetto compito di campionamento, che sarà tra i primi test della supremazia quantistica. Per capire il compito, immagina di avere una scatola piena di tessere. Ogni tessera ha inciso su 1 e 0 su di esso - 000, 010, 101 e così via.
Se ci sono solo tre bit, ci sono otto opzioni possibili. Ma ci possono essere più copie di ogni tessera etichettata nella casella. Potrebbero esserci 50 riquadri con etichetta 010 e 25 con etichetta 001. Questa distribuzione di tessere determina la probabilità che estragga casualmente una certa tessera. In questo caso, hai il doppio delle probabilità di tirare fuori una tessera con l'etichetta 010 dato che devi tirare fuori una tessera con l'etichetta 001.
Un compito di campionamento comporta un algoritmo informatico che equivale a raggiungere una scatola con una certa distribuzione di tessere e ne estrae a caso uno. Più è alta la probabilità specificata per qualsiasi tessera nella distribuzione, più è probabile che l'algoritmo emetta quella tessera.
Ovviamente, un algoritmo non raggiungerà una borsa letterale e non estrarrà tessere. Invece, produrrà in modo casuale un numero binario che è, per esempio, lungo 50 bit, dopo aver ricevuto una distribuzione che specifica la probabilità desiderata per ogni possibile stringa di output a 50 bit.
Se ci sono solo tre bit, ci sono otto opzioni possibili. Ma ci possono essere più copie di ogni tessera etichettata nella casella. Potrebbero esserci 50 riquadri con etichetta 010 e 25 con etichetta 001. Questa distribuzione di tessere determina la probabilità che estragga casualmente una certa tessera. In questo caso, hai il doppio delle probabilità di tirare fuori una tessera con l'etichetta 010 dato che devi tirare fuori una tessera con l'etichetta 001.
Un compito di campionamento comporta un algoritmo informatico che equivale a raggiungere una scatola con una certa distribuzione di tessere e ne estrae a caso uno. Più è alta la probabilità specificata per qualsiasi tessera nella distribuzione, più è probabile che l'algoritmo emetta quella tessera.
Ovviamente, un algoritmo non raggiungerà una borsa letterale e non estrarrà tessere. Invece, produrrà in modo casuale un numero binario che è, per esempio, lungo 50 bit, dopo aver ricevuto una distribuzione che specifica la probabilità desiderata per ogni possibile stringa di output a 50 bit.
Speriamo che questa sia la prima applicazione di un computer quantistico.
John Martinis
Per un computer classico, l'attività diventa esponenzialmente più difficile man mano che il numero di bit nella stringa aumenta. Ma per un computer quantistico, ci si aspetta che il compito rimanga relativamente semplice, indipendentemente dal fatto che coinvolga cinque bit o 50.
Il computer quantico inizia con tutti i suoi bit quantistici - qubit - in un certo stato. Diciamo che iniziano tutti a 0. Proprio come i computer classici agiscono su bit classici usando le cosiddette porte logiche, i computer quantistici manipolano i qubit usando l'equivalente quantistico, noto come porte quantistiche.
Ma le porte quantistiche possono mettere qubit in stati strani. Per esempio, un tipo di gate può mettere un qubit che inizia con un valore iniziale 0 in una sovrapposizione di 0 e 1. Se dovessi misurare lo stato del qubit, collasserebbe casualmente in 0 o 1 con uguale probabilità.
Ancor più bizzarramente, le porte quantistiche che agiscono su due o più qubit contemporaneamente possono far diventare i qubit "impigliati" l'uno con l'altro. In questo caso, gli stati dei qubit si intrecciano, così che i qubit possono ora essere descritti solo usando un singolo stato quantico.
Se metti insieme una serie di porte quantistiche, poi le fai agire su una serie di qubit in una sequenza specifica, hai creato un circuito quantico. Nel nostro caso, per generare in modo casuale una stringa a 50 bit, puoi costruire un circuito quantico che mette 50 qubit, presi insieme, in una sovrapposizione di stati che cattura la distribuzione che vorresti ricreare.
Quando i qubit vengono misurati, l'intera sovrapposizione collasserà casualmente su una stringa di 50 bit. La probabilità che collasserà su qualsiasi stringa determinata è dettata dalla distribuzione specificata dal circuito quantico. Misurare i qubit è come arrivare bendati nella scatola e campionare casualmente una stringa dalla distribuzione.
Il computer quantico inizia con tutti i suoi bit quantistici - qubit - in un certo stato. Diciamo che iniziano tutti a 0. Proprio come i computer classici agiscono su bit classici usando le cosiddette porte logiche, i computer quantistici manipolano i qubit usando l'equivalente quantistico, noto come porte quantistiche.
Ma le porte quantistiche possono mettere qubit in stati strani. Per esempio, un tipo di gate può mettere un qubit che inizia con un valore iniziale 0 in una sovrapposizione di 0 e 1. Se dovessi misurare lo stato del qubit, collasserebbe casualmente in 0 o 1 con uguale probabilità.
Ancor più bizzarramente, le porte quantistiche che agiscono su due o più qubit contemporaneamente possono far diventare i qubit "impigliati" l'uno con l'altro. In questo caso, gli stati dei qubit si intrecciano, così che i qubit possono ora essere descritti solo usando un singolo stato quantico.
Se metti insieme una serie di porte quantistiche, poi le fai agire su una serie di qubit in una sequenza specifica, hai creato un circuito quantico. Nel nostro caso, per generare in modo casuale una stringa a 50 bit, puoi costruire un circuito quantico che mette 50 qubit, presi insieme, in una sovrapposizione di stati che cattura la distribuzione che vorresti ricreare.
Quando i qubit vengono misurati, l'intera sovrapposizione collasserà casualmente su una stringa di 50 bit. La probabilità che collasserà su qualsiasi stringa determinata è dettata dalla distribuzione specificata dal circuito quantico. Misurare i qubit è come arrivare bendati nella scatola e campionare casualmente una stringa dalla distribuzione.
 |
| Scott Aaronson, scienziato informatico presso l'Università del Texas, ad Austin, afferma che la generazione casuale di numeri sarà probabilmente "la prima applicazione di computer quantistici che sarà tecnologicamente fattibile da implementare". Dipartimento di Informatica, Università del Texas ad Austin |
Come ci porta a numeri casuali? Fondamentalmente, la stringa a 50 bit campionata dal computer quantico avrà molta entropia, una misura di disordine o imprevedibilità e quindi casualità. "Questo potrebbe essere davvero un grosso problema", ha detto Scott Aaronson, uno scienziato informatico dell'Università del Texas, Austin, che ha elaborato il nuovo protocollo. "Non perché sia l'applicazione più importante dei computer quantistici - penso che sia lontana da quello - piuttosto, perché sembra probabilmente la prima applicazione di computer quantistici che sarà tecnologicamente fattibile da implementare".
Il protocollo di Aaronson per generare casualità è abbastanza semplice. Un computer classico prima raccoglie alcuni bit di casualità da qualche fonte attendibile e usa questa "casualità seme" per generare la descrizione di un circuito quantico. I bit casuali determinano i tipi di porte quantistiche e la sequenza in cui devono agire sui qubit. Il computer classico invia la descrizione al computer quantistico, che implementa il circuito quantico, misura i qubit e rimanda la stringa di bit di uscita a 50 bit. In tal modo, ha campionato a caso dalla distribuzione specificata dal circuito.
Ora ripeti il processo più e più volte, ad esempio 10 volte per ogni circuito quantico. Il computer classico utilizza test statistici per garantire che le stringhe di output abbiano molta entropia. Aaronson ha mostrato, in parte nel lavoro pubblicato con Lijie Chen e in parte nel lavoro ancora da pubblicare, che secondo certi plausibili presupposti che tali problemi sono computazionalmente difficili, nessun computer classico può generare tale entropia in qualsiasi momento del tempo necessario a un computer quantico campionare casualmente da una distribuzione. Dopo i controlli, il computer classico incolla tutte le stringhe di output a 50 bit e invia tutto a un noto algoritmo classico. "Produce una corda lunga che è quasi perfettamente casuale", ha detto Aaronson.
The Quantum Trapdoor
Il protocollo di Aaronson è più adatto per i computer quantistici con circa 50-100 qubit. Poiché il numero di qubit in un computer quantistico supera questa soglia, diventa computazionalmente intrattabile anche per i supercomputer classici che usano il protocollo. È qui che entra in scena un altro schema per generare casualità verificabile utilizzando computer quantistici. Usa una tecnica matematica esistente con un nome minaccioso: una botola senza artiglio. "Sembra molto peggio di così", ha detto Umesh Vazirani, un informatico dell'Università della California, Berkeley, che ha ideato la nuova strategia insieme a Zvika Brakerski, Paul Christiano, Urmila Mahadev e Thomas Vidick.
Immagina di nuovo una scatola. Invece di raggiungere ed estrarre una stringa, questa volta si rilascia una stringa di n bit, chiamarla x e si apre un'altra stringa di n bit. La scatola in qualche modo sta mappando una stringa di input su una stringa di output. Ma la scatola ha una proprietà speciale: per ogni x, c'è un'altra stringa di input y che genera la stessa stringa di output.
In altre parole, esistono due stringhe di input univoche, xey, per le quali la casella restituisce la stessa stringa di output, z. Questa tripletta di x, yez è chiamata artiglio. La scatola, nell'informatica, è una funzione. La funzione è facile da calcolare, il che significa che dato x o y, è facile calcolare z. Ma se ti danno solo x e z, trovare y - e quindi l'artiglio - è impossibile, anche per un computer quantistico.
Aggiornamento 21 giugno 2019: questo articolo è stato aggiornato per includere un riferimento al lavoro non pubblicato di Aaronson.
Il protocollo di Aaronson per generare casualità è abbastanza semplice. Un computer classico prima raccoglie alcuni bit di casualità da qualche fonte attendibile e usa questa "casualità seme" per generare la descrizione di un circuito quantico. I bit casuali determinano i tipi di porte quantistiche e la sequenza in cui devono agire sui qubit. Il computer classico invia la descrizione al computer quantistico, che implementa il circuito quantico, misura i qubit e rimanda la stringa di bit di uscita a 50 bit. In tal modo, ha campionato a caso dalla distribuzione specificata dal circuito.
Ora ripeti il processo più e più volte, ad esempio 10 volte per ogni circuito quantico. Il computer classico utilizza test statistici per garantire che le stringhe di output abbiano molta entropia. Aaronson ha mostrato, in parte nel lavoro pubblicato con Lijie Chen e in parte nel lavoro ancora da pubblicare, che secondo certi plausibili presupposti che tali problemi sono computazionalmente difficili, nessun computer classico può generare tale entropia in qualsiasi momento del tempo necessario a un computer quantico campionare casualmente da una distribuzione. Dopo i controlli, il computer classico incolla tutte le stringhe di output a 50 bit e invia tutto a un noto algoritmo classico. "Produce una corda lunga che è quasi perfettamente casuale", ha detto Aaronson.
The Quantum Trapdoor
Il protocollo di Aaronson è più adatto per i computer quantistici con circa 50-100 qubit. Poiché il numero di qubit in un computer quantistico supera questa soglia, diventa computazionalmente intrattabile anche per i supercomputer classici che usano il protocollo. È qui che entra in scena un altro schema per generare casualità verificabile utilizzando computer quantistici. Usa una tecnica matematica esistente con un nome minaccioso: una botola senza artiglio. "Sembra molto peggio di così", ha detto Umesh Vazirani, un informatico dell'Università della California, Berkeley, che ha ideato la nuova strategia insieme a Zvika Brakerski, Paul Christiano, Urmila Mahadev e Thomas Vidick.
Immagina di nuovo una scatola. Invece di raggiungere ed estrarre una stringa, questa volta si rilascia una stringa di n bit, chiamarla x e si apre un'altra stringa di n bit. La scatola in qualche modo sta mappando una stringa di input su una stringa di output. Ma la scatola ha una proprietà speciale: per ogni x, c'è un'altra stringa di input y che genera la stessa stringa di output.
In altre parole, esistono due stringhe di input univoche, xey, per le quali la casella restituisce la stessa stringa di output, z. Questa tripletta di x, yez è chiamata artiglio. La scatola, nell'informatica, è una funzione. La funzione è facile da calcolare, il che significa che dato x o y, è facile calcolare z. Ma se ti danno solo x e z, trovare y - e quindi l'artiglio - è impossibile, anche per un computer quantistico.
Aggiornamento 21 giugno 2019: questo articolo è stato aggiornato per includere un riferimento al lavoro non pubblicato di Aaronson.
 |
| Urmila Mahadev, Umesh Vazirani e Thomas Vidick (da sinistra) hanno sviluppato un generatore di numeri casuali collegando la crittografia con l'elaborazione di informazioni quantistiche. Jana Asenbrennerova per Quanta Magazine; Simons Institute per la teoria del calcolo; Per gentile concessione di Caltech |
L'unico modo per ottenere l'artiglio è se tu avessi delle informazioni interne, la cosiddetta botola.
Vazirani ed i suoi colleghi vogliono usare tali funzioni non solo per far sì che i computer quantistici generino casualità, ma per verificare che il computer quantico si stia comportando, beh, meccanicamente quantisticamente - il che è essenziale per fidarsi della casualità.
Il protocollo inizia con un computer quantico che mette n qubit in una sovrapposizione di tutte le stringhe n-bit. Quindi un computer classico invia una descrizione di un circuito quantistico specificando la funzione da applicare alla sovrapposizione - una funzione di artiglio senza botola. Il computer quantico implementa il circuito, ma senza sapere nulla della botola.
A questo punto, il computer quantico entra in uno stato in cui un set dei suoi qubit si trova in una sovrapposizione di tutte le stringhe n-bit, mentre un altro set contiene il risultato dell'applicazione della funzione a questa sovrapposizione. I due set di qubit sono impigliati l'uno con l'altro.
Il computer quantistico quindi misura il secondo set di qubit, collassando a caso la sovrapposizione in qualche output z. La prima serie di qubit, tuttavia, collassa in una sovrapposizione equa di due stringhe a n bit, x e y, perché entrambi potevano essere utilizzati come input per la funzione che portava a z.
Il computer classico riceve l'output z, quindi fa una delle due cose. Il più delle volte, chiede al computer quantico di misurare i suoi qubit rimanenti. Ciò collasserà la sovrapposizione, con una probabilità del 50%, in x o y. È equivalente a ottenere uno 0 o un 1, a caso.
Occasionalmente, per verificare la quantumness del computer quantistico, il computer classico richiede una misura speciale. La misurazione e il suo risultato sono progettati in modo che il computer classico, con l'aiuto della botola a cui solo ha accesso, possa garantire che il dispositivo che risponde alle sue domande sia effettivamente quantico. Vazirani e colleghi hanno dimostrato che se il dispositivo fornisce la risposta corretta alla misurazione speciale senza utilizzare qubit collassanti, è equivalente a capire l'artiglio senza usare la botola. Questo, ovviamente, è impossibile. Quindi deve esserci almeno un qubit che collassa all'interno del dispositivo (fornendo, a caso, uno 0 o un 1). "[Il protocollo] sta creando un qubit a prova di manomissione all'interno di un computer quantico non sicuro", ha detto Vazirani.
Vazirani ed i suoi colleghi vogliono usare tali funzioni non solo per far sì che i computer quantistici generino casualità, ma per verificare che il computer quantico si stia comportando, beh, meccanicamente quantisticamente - il che è essenziale per fidarsi della casualità.
Il protocollo inizia con un computer quantico che mette n qubit in una sovrapposizione di tutte le stringhe n-bit. Quindi un computer classico invia una descrizione di un circuito quantistico specificando la funzione da applicare alla sovrapposizione - una funzione di artiglio senza botola. Il computer quantico implementa il circuito, ma senza sapere nulla della botola.
A questo punto, il computer quantico entra in uno stato in cui un set dei suoi qubit si trova in una sovrapposizione di tutte le stringhe n-bit, mentre un altro set contiene il risultato dell'applicazione della funzione a questa sovrapposizione. I due set di qubit sono impigliati l'uno con l'altro.
Il computer quantistico quindi misura il secondo set di qubit, collassando a caso la sovrapposizione in qualche output z. La prima serie di qubit, tuttavia, collassa in una sovrapposizione equa di due stringhe a n bit, x e y, perché entrambi potevano essere utilizzati come input per la funzione che portava a z.
Il computer classico riceve l'output z, quindi fa una delle due cose. Il più delle volte, chiede al computer quantico di misurare i suoi qubit rimanenti. Ciò collasserà la sovrapposizione, con una probabilità del 50%, in x o y. È equivalente a ottenere uno 0 o un 1, a caso.
Occasionalmente, per verificare la quantumness del computer quantistico, il computer classico richiede una misura speciale. La misurazione e il suo risultato sono progettati in modo che il computer classico, con l'aiuto della botola a cui solo ha accesso, possa garantire che il dispositivo che risponde alle sue domande sia effettivamente quantico. Vazirani e colleghi hanno dimostrato che se il dispositivo fornisce la risposta corretta alla misurazione speciale senza utilizzare qubit collassanti, è equivalente a capire l'artiglio senza usare la botola. Questo, ovviamente, è impossibile. Quindi deve esserci almeno un qubit che collassa all'interno del dispositivo (fornendo, a caso, uno 0 o un 1). "[Il protocollo] sta creando un qubit a prova di manomissione all'interno di un computer quantico non sicuro", ha detto Vazirani.
Questo qubit a prova di manomissione fornisce un bit di informazioni veramente casuali per ogni interrogazione; una sequenza di tali query può quindi essere utilizzata per creare stringhe di bit lunghe e casuali.
Questo schema potrebbe essere più veloce del protocollo di campionamento quantistico di Aaronson, ma ha uno svantaggio ben definito. "Non sarà pratico con 50 o 70 qubit", ha detto Aaronson.
Aaronson, per ora, sta aspettando il sistema di Google. "Se la cosa che stanno per far uscire sarà effettivamente abbastanza buona da ottenere la supremazia quantistica è una grande domanda", ha detto.
Se lo è, allora la casualità quantistica verificabile da un singolo dispositivo quantistico è dietro l'angolo. "Pensiamo che sia utile e un mercato potenziale, e questo è qualcosa che vogliamo pensare di offrire alle persone", ha detto Martinis.
Questo articolo è stato ristampato su Wired.com
Questo schema potrebbe essere più veloce del protocollo di campionamento quantistico di Aaronson, ma ha uno svantaggio ben definito. "Non sarà pratico con 50 o 70 qubit", ha detto Aaronson.
Aaronson, per ora, sta aspettando il sistema di Google. "Se la cosa che stanno per far uscire sarà effettivamente abbastanza buona da ottenere la supremazia quantistica è una grande domanda", ha detto.
Se lo è, allora la casualità quantistica verificabile da un singolo dispositivo quantistico è dietro l'angolo. "Pensiamo che sia utile e un mercato potenziale, e questo è qualcosa che vogliamo pensare di offrire alle persone", ha detto Martinis.
Questo articolo è stato ristampato su Wired.com
Nessun commento:
Posta un commento
Nota. Solo i membri di questo blog possono postare un commento.