A brief history of quantum vs classical computational advantage

Questo articolo di rassegna riassume in modo completo tutti gli esperimenti che rivendicano un vantaggio computazionale quantistico, esamina criticamente le loro sfide e le confutazioni, discute i vantaggi teorici in problemi specifici e mette in evidenza i recenti progressi nella correzione degli errori quantistici come passo fondamentale verso il raggiungimento di un vantaggio nell'algoritmo di Shor.

L'essenziale

Il Quadro Generale: La Grande Gara

Immagina una gara tra due corridori: Computer Classici (i maratoneti super-veloci e affidabili che usiamo oggi) e Computer Quantistici (i corridori misteriosi e fulminei che operano secondo le strane regole della fisica quantistica).

L'obiettivo di questo documento è tenere un tabellone segnapunti di ogni volta che il Corridore Quantistico ha dichiarato: "Posso risolvere questo specifico puzzle più velocemente del Corridore Classico!". L'autore, Ryan LaRose, agisce come uno storico dello sport, rivedendo ogni gara, ogni protesta e ogni squalifica per dirci esattamente dove si trova la gara oggi.

Il documento definisce "vantaggio" semplicemente: Chi finisce il compito per primo? Non importa se il compito è utile (come curare una malattia) o solo un puzzle sciocco; l'unica domanda è la velocità.

---

Parte 1: Le Gare dei "Puzzle Sciocchi" (Vantaggio Sperimentale)

Finora, i Corridori Quantistici hanno provato a vincere tre tipi specifici di gare "sciocche". Queste non sono ancora utili per costruire ponti o scrivere email; sono progettate specificamente per essere difficili per i computer classici ma facili per quelli quantistici.

1. La Gara del Campionamento di Circuiti Casuali (Il Caos del "Lancio della Moneta")

• Il Compito: Immagina una macchina che lancia 53 monete contemporaneamente in modo completamente casuale e caotico. Il computer quantistico lo fa e registra il pattern di teste e croci. Il computer classico deve indovinare quale sarebbe stato il pattern.
• La Prima Vittoria (Google, 2019): Il computer "Sycamore" di Google ha fatto questo in 200 secondi. Hanno affermato che un supercomputer classico avrebbe impiegato 10.000 anni per fare lo stesso calcolo.
• La Controffensiva: I corridori classici non si sono arresi. Hanno inventato nuovi modi più intelligenti per risolvere il puzzle.
  • Analogia: Immagina che il corridore classico si sia reso conto di non aver bisogno di percorrere l'intera pista; poteva prendere una scorciatoia attraverso un tunnel che aveva trovato.
  • Il Risultato: Nel tempo, i computer classici sono diventati più veloci. Entro il 2024, un supercomputer classico è riuscito a svolgere lo stesso compito in 86 secondi, battendo il computer quantistico.
• Il Verdetto: La prima vittoria di Google è stata "smentita". Il corridore classico li ha raggiunti e superati. Tuttavia, Google ha riprovato con puzzle più grandi e difficili (più monete, più lanci), e quelle gare più recenti sono ancora non smentite.

2. La Gara del Campionamento di Bosoni Gaussiani (Il "Flipper di Fotoni")

• Il Compito: Invece di monete, questa gara usa particelle di luce (fotoni) che rimbalzano attraverso un labirinto di specchi. Il computer quantistico li spara dentro e atterrano in punti specifici. Il computer classico deve calcolare dove sono atterrati.
• I Concorrenti: Team dalla Cina (USTC) e dal Canada (Xanadu) hanno costruito questi corridori basati sulla luce.
• La Controffensiva: Proprio come nella gara delle monete, i computer classici hanno trovato "scappatoie". Hanno realizzato che se le particelle di luce non fossero perfette (cosa che non sono mai), il calcolo diventava più facile. Hanno costruito nuovi algoritmi per simulare il labirinto di luce molto più velocemente del previsto.
• Il Verdetto: La maggior parte di queste affermazioni è stata "debolmente smentita". Questo significa che i computer classici non hanno ancora battuto quelli quantistici sui puzzle più grandi, ma sono abbastanza vicini che un computer classico leggermente migliore nel prossimo futuro potrebbe probabilmente riuscirci.

3. La Gara di Simulazione Quantistica (La "Previsione Meteo")

• Il Compito: Simulare come un sistema complesso (come un materiale magnetico) cambia nel tempo.
• I Concorrenti: IBM e D-Wave.
• La Controffensiva: IBM ha affermato di aver simulato un sistema magnetico più velocemente di un computer classico. Ma entro due settimane, ricercatori classici hanno dimostrato di poterlo simulare su un portatile in pochi minuti.
• Il Verdetto: L'affermazione di IBM è stata rapidamente "smentita". Il corridore classico ha trovato un percorso molto più veloce. Il recente tentativo di D-Wave è ancora sotto osservazione, ma è probabile che affronti sfide simili.

---

Parte 2: Le Gare "Teoriche" (Le Dimostrazioni Matematiche)

A volte, i matematici dicono: "Se costruiamo un computer quantistico perfetto, dovrebbe vincere questa gara". Ma la storia mostra che i matematici classici sono molto bravi a trovare nuovi trucchi.

• La Gara del Sistema di Raccomandazione: È stato proposto un algoritmo quantistico per raccomandare film a te più velocemente di qualsiasi computer classico.
  • La Svista: Un matematico classico (Ewin Tang) ha realizzato: "Ehi, se diamo al computer classico la stessa struttura dati speciale che usa quello quantistico, può risolvere il problema alla stessa velocità!"
  • Il Risultato: Il vantaggio quantistico è svanito. Questo è chiamato "dequantizzazione".
• La Gara di Ottimizzazione: Storie simili sono accadute con algoritmi progettati per risolvere problemi complessi di schedulazione. Il vantaggio quantistico è stato affermato, e poi è stato trovato un algoritmo classico che era altrettanto buono.

---

Parte 3: L'Ultima Frontiera (Correzione degli Errori)

Qui è la conclusione più importante del documento: I computer quantistici sono fragili.

• L'Analogia: Immagina che il Corridore Quantistico sia un corridore di vetro. È incredibilmente veloce, ma se inciampa su un sassolino minuscolo (rumore), si frantuma. Per correre una maratona (come fattorizzare numeri grandi per rompere la crittografia), deve indossare un'armatura.
• L'Armatura: Questa armatura è chiamata Correzione degli Errori Quantistici. Usa molti "qubit" fisici di "vetro" per creare un unico robusto "qubit" logico.
• Lo Stato Attuale: Stiamo appena iniziando a costruire questa armatura.
  • Nel 2024, Google ha annunciato un nuovo chip (Willow) in cui il "qubit" logico (quello corazzato) è durato più a lungo dei singoli "qubit" fisici (quelli di vetro).
  • Questo è il momento del "Santo Graal". Dimostra che aggiungere più parti per correggere gli errori rende effettivamente il sistema migliore, non peggiore.
• Il Futuro: Finché non avremo questa armatura, non possiamo correre le gare "utili" (come rompere codici o simulare nuovi farmaci). Il documento sostiene che la Correzione degli Errori è l'ultima frontiera prima che i computer quantistici possano davvero battere quelli classici su problemi del mondo reale.

Riepilogo: Dove Ci Troviamo?

Il documento conclude che la gara è una lotta di forza.

1. I computer quantistici fanno un grande balzo in avanti.
2. I computer classici diventano più intelligenti, trovano scorciatoie e li raggiungono (o li superano).
3. I computer quantistici costruiscono hardware migliore e riprovano.

Ora, siamo sul confine. Abbiamo visto computer quantistici vincere su puzzle specifici e inutili, ma i computer classici hanno trovato modi per batterli su quasi tutti. Il documento suggerisce che affinché i computer quantistici vincano una gara utile, devono prima padroneggiare l'arte della Correzione degli Errori. Fino ad allora, il vantaggio continuerà a cambiare mano.

Sommario tecnico

Titolo: Una Breve Storia del Vantaggio Computazionale Quantistico rispetto a quello Classico
Autori: Ryan LaRose
Fonte: Quantum (Accettato il 14-05-2026)

Enunciato del Problema

Il documento affronta il panorama in evoluzione del "vantaggio computazionale quantistico" (definito anche supremazia quantistica o computazione oltre-classica). Il problema centrale consiste nel definire e tracciare il confine mutevole tra ciò che è computazionalmente fattibile per i computer classici rispetto ai computer quantistici. Gli autori definiscono il vantaggio computazionale specificamente come una riduzione del tempo di soluzione per un dato problema, indipendentemente dall'utilità pratica del problema stesso. La rassegna mira a catalogare tutte le affermazioni sperimentali di vantaggio quantistico fino ad oggi, insieme alle successive sfide classiche, smentite e sviluppi teorici che hanno alterato lo status di tali affermazioni.

Metodologia

Il documento adotta una metodologia di rassegna completa, sintetizzando dati storici provenienti dalla fisica sperimentale, dall'informatica e dalla teoria della complessità.

1. Catalogazione Cronologica: Gli autori compilano una cronologia di tutti gli esperimenti che rivendicano un vantaggio quantistico, categorizzandoli per tipo di problema: Campionamento di Circuiti Casuali (RCS), Campionamento di Bosoni Gaussiani (GBS) e Simulazione Quantistica (QSim).
2. Classificazione dello Status: Ogni esperimento riceve uno status basato sulla letteratura successiva:
   • Non Smentito: Nessun algoritmo classico ha ancora simulato l'esperimento più velocemente.
   • Sfidiato: Gli algoritmi classici hanno migliorato i tempi di simulazione o messo in discussione aspetti specifici dell'esperimento.
   • Debolmente Smentito: Esiste un algoritmo classico che potrebbe probabilmente simulare l'esperimento su hardware classico di prossima generazione.
   • Smentito: Un computer classico ha simulato con successo l'esperimento più velocemente del dispositivo quantistico.
3. Analisi Teorica: La rassegna esamina il vantaggio teorico in domini specifici (ottimizzazione approssimata, sistemi di raccomandazione, chimica quantistica) per evidenziare come la "dequantizzazione" (lo sviluppo di algoritmi classici ispirati a quelli quantistici) possa erodere i vantaggi di velocità teorici.
4. Rassegna sulla Correzione degli Errori: Il documento traccia la storia degli esperimenti di correzione quantistica degli errori (QEC), identificandoli come la necessaria "ultima frontiera" per raggiungere il vantaggio in algoritmi come quello di Shor, che richiedono tolleranza ai guasti.

Contributi Chiave

• Tabella Completa degli Status: Il documento fornisce la Tabella 1, un elenco cronologico di tutte le affermazioni di vantaggio quantistico (dal Sycamore di Google del 2019 alla simulazione di D-Wave del 2024) e la loro attuale posizione riguardo alla smentita classica.
• Narrazione Dettagliata delle Sfide: Documenta la "gara di armamenti" tra esperimenti quantistici e simulazione classica. Contributi degni di nota includono il monitoraggio delle ottimizzazioni nella contrazione delle reti tensoriali (ad esempio, algoritmi "big head", partizionamento di ipergrafi) e strategie di sfruttamento del rumore che hanno ridotto i tempi di esecuzione classici stimati da migliaia di anni a ore o secondi per esperimenti specifici.
• Chiarimento delle Metriche: La rassegna analizza criticamente la fedeltà del Benchmark di Entropia Incrociata (XEB), discutendo le falle in cui gli algoritmi classici possono "falsificare" valori XEB elevati senza simulare l'intero circuito, e distinguendo tra smentite deboli e forti.
• Dequantizzazione Teorica: Il documento dettaglia come i vantaggi teorici nell'ottimizzazione Max-E3LIN2 e nei sistemi di raccomandazione siano stati persi quando algoritmi classici (ad esempio, di Barak et al. ed Ewin Tang) hanno eguagliato o superato le prestazioni quantistiche sotto assunzioni di input simili.
• Progressi nella QEC: La Tabella 2 e la Sezione 4 riassumono il rapido progresso degli esperimenti di correzione degli errori, notando la transizione da semplici codici di ripetizione a codici di superficie con distanze fino a 7, e il recente traguardo dell'esperimento di Google del 2024 in cui i tassi di errore logico sono scesi sotto la soglia del tasso di errore fisico.

Risultati

• Volatilità Sperimentale: La rassegna rileva che quasi ogni affermazione sperimentale maggiore di vantaggio quantistico ha affrontato sfide significative.
  • RCS di Google del 2019 (53 qubit): Inizialmente rivendicato un tempo di esecuzione classico di 10.000 anni. Ciò è stato sfidato da ottimizzazioni delle reti tensoriali e infine fortemente smentito nel 2024 (Zhao et al.) utilizzando 1.432 GPU per simulare l'esperimento in 86,4 secondi.
  • GBS di USTC (Jiuzhang 1.0, 2.0, 3.0): Le affermazioni di vantaggio sono state debolmente smentite da Oh et al. (2023), che hanno utilizzato reti tensoriali per simulare questi esperimenti significativamente più velocemente dei dispositivi quantistici, sebbene gli esperimenti rimangano non smentiti nel senso "forte" per le istanze più grandi.
  • QSim di IBM (2023): Un'affermazione di vantaggio nella simulazione del modello di Ising a campo trasverso è stata smentita nel giro di poche settimane da molteplici approcci classici (reti tensoriali, propagazione delle credenze, teoria delle perturbazioni di Clifford) eseguiti su laptop o singole GPU.
  • D-Wave (2024): Una recente affermazione di vantaggio nella simulazione quantistica rimane non smentita al momento della stesura, sebbene gli autori notino che è probabile che diventi un bersaglio per future sfide classiche.
• Spostamenti Teorici: Il documento dimostra che il vantaggio teorico non è statico. Gli algoritmi per i sistemi di raccomandazione e l'ottimizzazione approssimata (QAOA) hanno visto i loro vantaggi quantistici erosi da algoritmi classici "dequantizzati" che utilizzano strutture dati o tecniche di approssimazione simili.
• Traguardi nella Correzione degli Errori: Sebbene il calcolo quantistico tollerante ai guasti non sia ancora realizzato, la rassegna evidenzia che i qubit logici stanno ora raggiungendo durate di vita superiori ai loro componenti fisici e che i tassi di errore si stanno avvicinando alla soglia richiesta per una tolleranza ai guasti scalabile.

Significato e Affermazioni

Il documento afferma che la storia del vantaggio quantistico è un bersaglio dinamico e mutevole piuttosto che un risultato statico.

• Bersaglio Mobile: Gli autori sottolineano che il vantaggio computazionale è definito rispetto ai migliori noti algoritmi e hardware classici in un momento specifico. Man mano che gli algoritmi classici migliorano (spesso ispirati da intuizioni quantistiche), il confine del vantaggio si sposta nuovamente verso i computer classici.
• Crisi di Verifica: Una parte significativa del documento evidenzia la difficoltà di verificare il vantaggio quantistico. Molti esperimenti attuali (come l'RCS) sono difficili da verificare classicamente, creando un paradosso in cui l'affermazione di vantaggio si basa su calcoli classici che sono essi stessi intrattabili. Il documento indica il "campionamento di circuiti piccati" e il "Campionamento di Codice Nascosto" come direzioni future proposte per un vantaggio verificabile in modo efficiente.
• Il Ruolo della Correzione degli Errori: La rassegna postula che per gli algoritmi con accelerazioni esponenziali dimostrate (come l'algoritmo di Shor), l'"ultima frontiera" non è solo il numero di qubit, ma la correzione quantistica degli errori. Senza tolleranza ai guasti, l'overhead della correzione degli errori potrebbe annullare qualsiasi accelerazione teorica.
• Prospettiva Modesta: Gli autori concludono che, sebbene il vantaggio quantistico sia probabile per problemi specifici, il campo si trova attualmente sul "confine" tra dominio quantistico e classico. Sconsigliano di assumere un vantaggio permanente, notando che lo status continuerà probabilmente a spostarsi mentre le tecnologie classiche e quantistiche evolvono. Il documento funge da registro storico per spingere i ricercatori verso nuove formulazioni di problemi che sono classicamente difficili, quantisticamente facili, efficientemente verificabili e scientificamente utili.