In quali casi specifici i computer quantistici superano le loro controparti classiche? È una domanda difficile a cui rispondere, in parte perché i computer quantistici di oggi sono cose pignoli, afflitti da errori che possono accumularsi e rovinare i loro calcoli.

Di una misura, ovviamente, l'hanno già fatto. Nel 2019, i fisici di Google ha annunciato che hanno utilizzato una macchina a 53 qubit per raggiungere supremazia quantistica, una pietra miliare simbolica che segna il punto in cui un computer quantistico fa qualcosa al di là della portata di qualsiasi algoritmo pratico classico. Simile dimostrazioni seguì presto dai fisici dell'Università di Scienza e Tecnologia della Cina.

 

Ma piuttosto che concentrarsi su un risultato sperimentale per una particolare macchina, gli informatici vogliono sapere se gli algoritmi classici saranno in grado di tenere il passo man mano che i computer quantistici diventano sempre più grandi. "La speranza è che alla fine il lato quantistico si allontani completamente fino a quando non ci sarà più concorrenza", ha detto Scott Aaronson, un informatico dell'Università del Texas, Austin.

 

A questa domanda generale è ancora difficile rispondere, sempre in parte a causa di quei fastidiosi errori. (Le future macchine quantistiche compenseranno le loro imperfezioni usando una tecnica chiamata correzione di errori quantistici, ma quella capacità è ancora lontana.) È possibile ottenere l'auspicato vantaggio quantistico anche con errori non corretti?

 

La maggior parte dei ricercatori sospettava che la risposta fosse no, ma non potevano provarla per tutti i casi. Ora, in un carta pubblicato sul server di prestampa arxiv.org, un team di scienziati informatici ha compiuto un passo importante verso la prova completa che la correzione degli errori è necessaria per un vantaggio quantistico duraturo nel campionamento casuale dei circuiti, il problema su misura che Google ha utilizzato per mostrare la supremazia quantistica. Lo hanno fatto sviluppando un algoritmo classico in grado di simulare esperimenti di campionamento di circuiti casuali quando sono presenti errori.

"È un bel risultato teorico", ha detto Aaronson sottolineando che il nuovo algoritmo non è praticamente utile per simulare esperimenti reali come quello di Google.

 

Negli esperimenti di campionamento di circuiti casuali, i ricercatori iniziano con una serie di qubit o bit quantici. Quindi manipolano casualmente questi qubit con operazioni chiamate porte quantistiche. Alcuni gate causano l'entanglement di coppie di qubit, il che significa che condividono uno stato quantico e non possono essere descritti separatamente. Strati ripetuti di porte portano i qubit in uno stato entangled più complicato.

 

Per conoscere quello stato quantico, i ricercatori misurano quindi tutti i qubit nell'array. Ciò fa collassare il loro stato quantico collettivo in una stringa casuale di bit ordinari: 0 e 1. Il numero di possibili risultati cresce rapidamente con il numero di qubit nell'array: con 53 qubit, come nell'esperimento di Google, sono quasi 10 quadrilioni. E non tutte le stringhe sono ugualmente probabili. Campionare da un circuito casuale significa ripetere tali misurazioni molte volte per costruire un quadro della distribuzione di probabilità alla base dei risultati.

 

La questione del vantaggio quantistico è semplicemente questa: è difficile imitare quella distribuzione di probabilità con un algoritmo classico che non utilizza alcun entanglement?

 

In 2019, i ricercatori dimostrato che la risposta è sì per circuiti quantistici privi di errori: è davvero difficile simulare classicamente un esperimento di campionamento di circuiti casuali quando non ci sono errori. I ricercatori hanno lavorato nell'ambito della teoria della complessità computazionale, che classifica la relativa difficoltà di diversi problemi. In questo campo, i ricercatori non trattano il numero di qubit come un numero fisso come 53. n, che è un numero che aumenterà”, ha detto Aram Harrow, un fisico del Massachusetts Institute of Technology. “Allora vuoi chiedere: stiamo facendo cose in cui lo sforzo è esponenziale n o polinomio in n?” Questo è il modo migliore per classificare il tempo di esecuzione di un algoritmo: quando n diventa abbastanza grande, un algoritmo esponenziale n è molto indietro rispetto a qualsiasi algoritmo che è polinomiale n. Quando i teorici parlano di un problema difficile per i computer classici ma facile per i computer quantistici, si riferiscono a questa distinzione: il miglior algoritmo classico richiede tempo esponenziale, mentre un computer quantistico può risolvere il problema in tempo polinomiale.

Eppure quel documento del 2019 ignorava gli effetti degli errori causati da cancelli imperfetti. Ciò ha lasciato aperto il caso di un vantaggio quantistico per il campionamento casuale del circuito senza correzione degli errori.

 

Se immagini di aumentare continuamente il numero di qubit come fanno i teorici della complessità, e vuoi anche tenere conto degli errori, devi decidere se continuare ad aggiungere altri strati di porte, aumentando la profondità del circuito, come dicono i ricercatori. Supponiamo di mantenere costante la profondità del circuito, diciamo, a tre strati relativamente poco profondi, aumentando il numero di qubit. Non otterrai molto entanglement e l'output sarà comunque suscettibile di simulazione classica. D'altra parte, se si aumenta la profondità del circuito per tenere il passo con il crescente numero di qubit, gli effetti cumulativi degli errori di gate elimineranno l'entanglement e l'output diventerà nuovamente facile da simulare in modo classico.

 

Ma nel mezzo c'è una zona di Riccioli d'oro. Prima del nuovo documento, c'era ancora la possibilità che il vantaggio quantistico potesse sopravvivere qui, anche se il numero di qubit aumentava. In questo caso di profondità intermedia, aumenti la profondità del circuito molto lentamente man mano che il numero di qubit cresce: anche se l'output verrà costantemente degradato da errori, potrebbe essere comunque difficile simulare in modo classico a ogni passaggio.

Il nuovo documento colma questa scappatoia. Gli autori hanno derivato un algoritmo classico per simulare il campionamento casuale del circuito e hanno dimostrato che il suo tempo di esecuzione è una funzione polinomiale del tempo necessario per eseguire il corrispondente esperimento quantistico. Il risultato forgia una stretta connessione teorica tra la velocità degli approcci classici e quantistici al campionamento casuale dei circuiti.

 

Il nuovo algoritmo funziona per un'ampia classe di circuiti di profondità intermedia, ma i suoi presupposti sottostanti si rompono per alcuni circuiti meno profondi, lasciando un piccolo spazio in cui i metodi di simulazione classici efficienti sono sconosciuti. Ma pochi ricercatori nutrono la speranza che il campionamento casuale del circuito si dimostri difficile da simulare in modo classico in questa finestra ristretta rimanente. "Gli do probabilità piuttosto piccole", ha detto Bill Feffermann, un informatico dell'Università di Chicago e uno degli autori dell'articolo teorico del 2019.

 

Il risultato suggerisce che il campionamento casuale dei circuiti non produrrà un vantaggio quantistico secondo i rigorosi standard della teoria della complessità computazionale. Allo stesso tempo, illustra il fatto che gli algoritmi polinomiali, che i teorici della complessità chiamano indiscriminatamente efficienti, non sono necessariamente veloci nella pratica. Il nuovo algoritmo classico diventa progressivamente più lento man mano che il tasso di errore diminuisce e, con i bassi tassi di errore raggiunti negli esperimenti di supremazia quantistica, è troppo lento per essere pratico. Senza errori, si rompe del tutto, quindi questo risultato non contraddice nulla che i ricercatori sapessero su quanto sia difficile simulare classicamente il campionamento casuale del circuito nel caso ideale e privo di errori. Sergio Boixo, il fisico che guida la ricerca sulla supremazia quantistica di Google, afferma di considerare il documento "più come una bella conferma del campionamento casuale del circuito che altro".

 

Su un punto, tutti i ricercatori concordano: il nuovo algoritmo sottolinea quanto sarà cruciale la correzione degli errori quantistici per il successo a lungo termine del calcolo quantistico. "Questa è la soluzione, alla fine della giornata", ha detto Fefferman.

Traduci »