⚛️ quantum physics

Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem

Questo articolo introduce Quantum WalkScore (QWS), un benchmark scalabile e orientato alle applicazioni che valuta le prestazioni dei computer quantistici NISQ e futuri computer quantistici tolleranti ai guasti misurando la loro capacità di risolvere il problema della ricerca di nodi in un grafo utilizzando camminate quantistiche a tempo discreto e amplificazione dell'ampiezza, validato sia tramite simulazioni che attraverso esperimenti su processori quantistici IBM.

Autori originali: Noé Olivier, Michel Nowak

Pubblicato 2026-09-18

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Noé Olivier, Michel Nowak

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nella ricerca di macchine capaci di risolvere problemi che vanno oltre la portata degli odierni supercomputer, gli scienziati stanno correndo per sviluppare i computer quantistici. Questi dispositivi non si affidano ai semplici interruttori on-off dei bit classici, ma utilizzano invece i bit quantistici, o qubit, che possono esistere in più stati contemporaneamente. Questa proprietà unica permette loro di esplorare simultaneamente vaste possibilità. Tuttavia, costruire una macchina capace di mantenere in modo affidabile questi fragili stati quantistici è incredibilmente difficile. Gli attuali dispositivi sono spesso afflitti da rumore ed errori, portando i ricercatori a porsi una domanda critica: come facciamo a sapere se un computer quantistico stia effettivamente funzionando e quanto sia bravo a risolvere compiti del mondo reale? Per rispondere a ciò, la comunità scientifica ha bisogno di qualcosa di più di un semplice elenco di tassi di errore; ha bisogno di un test pratico che misuri se una macchina può navigare con successo un problema complesso.

Un team di ricercatori presso CortAIx Labs in Francia ha proposto un nuovo modo per misurare questa capacità, chiamato Quantum WalkScore. Invece di testare proprietà matematiche astratte, il loro benchmark chiede al computer di eseguire un compito specifico e utile: trovare un obiettivo nascosto all'interno di una rete. Immaginate un viaggiatore che cerca di trovare una città specifica in una vasta mappa di strade collegate. Un computer classico controllerebbe le strade una alla volta, ma un computer quantistico può esplorare molti percorsi contemporaneamente. I ricercatori si sono concentrati su due potenti strumenti che i computer quantistici utilizzano per questo tipo di ricerca: un metodo chiamato camminata quantistica a tempo discreto (discrete-time quantum walk), che agisce come un modo sofisticato di muoversi attraverso la rete, e una tecnica chiamata amplificazione dell'ampiezza, che aumenta le probabilità di trovare la risposta corretta. Combinando questi strumenti, il team ha creato un test che misura quanto una rete possa essere grande prima che il rumore nella macchina causi il suo fallimento.

Il benchmark è progettato per essere scalabile, il che significa che può partire da una rete molto piccola e crescere in dimensioni e complessità man mano che l'hardware migliora. I ricercatori hanno testato questo protocollo su due tipi di forme di rete: un semplice anello, dove ogni punto si connette a due vicini, e una griglia più complessa che si avvolge su se stessa, come la superficie di una ciambella. Hanno definito un obiettivo chiaro: il computer deve trovare l'obiettivo nascosto con un tasso di successo superiore a quello che sarebbe atteso dal puro caso. Se il computer ha successo, il test passa a una versione leggermente più grande o più difficile del problema. Il punteggio finale è semplicemente la dimensione della rete più grande che il computer è riuscito a risolvere prima di non essere più in grado di trovare l'obiettivo in modo affidabile. Questo approccio fornisce un numero concreto che chiunque può comprendere, rappresentando il limite pratico della capacità attuale della macchina.

Per vedere come questo funzioni in pratica, i ricercatori hanno eseguito i loro test su diverse generazioni di processori quantistici reali forniti da IBM, inclusi i modelli chiamati Heron e Nighthawk. Hanno anche eseguito simulazioni su un computer perfetto e privo di rumore per vedere quali dovrebbero essere i risultati in un mondo ideale. Le simulazioni hanno mostato che, con le impostazioni corrette, gli algoritmi quantistici potrebbero teoricamente risolvere problemi molto grandi, trovando l'obiettivo con alta fiducia. Tuttavia, quando il team ha eseguito gli stessi test sulle macchine fisiche reali, i risultati sono stati molto più modesti. Il rumore e gli errori inerenti all'attuale hardware hanno fatto sì che i computer potessero risolvere con successo solo reti molto piccole. Per le reti a forma di anello, le macchine con le migliori prestazioni sono riuscite a trovare l'obiettivo in reti di una dimensione specifica, ma man mano che la rete cresceva, il tasso di successo scendeva al livello di un tentativo casuale.

Lo studio evidenzia un divario significativo tra ciò che gli algoritmi quantistici possono fare in teoria e ciò che l'attuale hardware può effettivamente raggiungere. I ricercatori hanno scoperto che la complessità del circuito richiesto per eseguire la ricerca cresce rapidamente man mano che il problema diventa più grande. Sulle macchine testate, i circuiti troppo profondi o complessi sono stati sopraffatti dagli errori, causando la degradazione dell'informazione quantistica prima che la risposta potesse essere trovata. Anche con i processori più avanzati disponibili al momento dello studio, il team è riuscito a dimostrare solo un punteggio di prova di concetto, provando che il metodo funziona ma rivelando anche quanto l'hardware debba ancora migliorare. I risultati suggeriscono che, sebbene gli strumenti matematici siano pronti, le macchine fisiche sono ancora nelle prime fasi della capacità di gestire i compiti impegnativi richiesti per applicazioni del mondo reale come la logistica o la ricerca in database.

Questo nuovo benchmark, Quantum WalkScore, offre un modo chiaro e onesto per tracciare i progressi. Non si basa sul potenziale teorico o su simulazioni idealizzate, ma misura la prestazione effettiva della macchina in modo controllato e ripetibile. Stabilendo uno standard che richiede al computer di battere il caso casuale su un problema specifico di grafi, i ricercatori forniscono un metro di paragone per l'intero campo. Man mano che l'hardware quantistico evolve, diventando più stabile e meno incline agli errori, questo punteggio aumenterà naturalmente. Il lavoro funge da promemoria del fatto che il percorso verso il potente calcolo quantistico è una salita graduale, dove ogni passo verso l'alto nelle prestazioni deve essere verificato risolvendo con successo un problema che prima era fuori portata. I ricercatori hanno tracciato una mappa per questo viaggio, mostrando esattamente dove si trovano le macchine oggi e cosa devono superare per raggiungere il futuro.

Sintesi Tecnica: Quantum WalkScore (QWS)

Definizione del Problema
Il documento affronta la necessità di benchmark orientati alle applicazioni per valutare la maturità dei computer quantistici NISQ (Noisy Intermediate-Scale Quantum) e dei futuri computer quantistici tolleranti ai guasti. Mentre i benchmark esistenti si concentrano sulla fedeltà delle porte fisiche o sul campionamento di circuiti casuali, vi è una scarsità di benchmark che utilizzino routine quantistiche promettenti, specificamente il Cammino Quantistico a Tempo Discreto (DTQW) e l'Amplificazione dell'Ampiezza (AA), per risolvere problemi pratici su grafi. Gli autori si concentrano sul problema di ricerca del nodo nel grafo: identificare un nodo target specifico $v_t$ all'interno di un grafo non orientato partendo da un nodo sorgente $v_0$ . Questo problema funge da blocco fondamentale per applicazioni reali come il routing nelle telecomunicazioni, la ricerca in database e l'analisi di reti complesse.

Metodologia: Il Protocollo Quantum WalkScore (QWS)
Gli autori propongono il Quantum WalkScore (QWS), un protocollo di benchmark scalabile progettato per misurare la dimensione massima del problema che un computer quantistico può risolvere con successo.

Famiglie di Grafi: Il benchmark utilizza due specifiche topologie di grafi per bilanciare semplicità, scalabilità e applicabilità all'hardware:
1. Grafi Ciclici: Strutture 1D con $2^n$ nodi, dove ogni nodo si connette a due vicini.
2. Grafi Torus 2D: Strutture 2D con $2^n \times 2^n$ nodi, dove ogni nodo si connette a quattro vicini (condizioni al contorno periodiche).
Istanza del Problema: Definita da $(n, d)$ , dove $n$ è il numero di qubit e $d$ è la distanza (percorsi minimi di archi) tra il nodo sorgente e il nodo target.
Routine Algoritmica:
1. Inizializzazione: Il sistema viene inizializzato nello stato $|v_0\rangle$ .
2. Cammino Quantistico a Tempo Discreto (DTQW): Il camminatore evolve per $num\_w$ passi. Il protocollo richiede $num\_w \ge d$ e $num\_w \equiv d \pmod 2$ per garantire la raggiungibilità. Viene utilizzata una moneta di Hadamard per un cammino non polarizzato.
3. Amplificazione dell'Ampiezza (AA): La routine DTQW è inserita all'interno di un framework di AA (Brassard et al.) per aumentare la probabilità di misurare lo stato target. Ciò comporta $num\_aa$ iterazioni di riflessione rispetto al target e allo stato iniziale.
4. Misurazione: La probabilità di successo $p_{exp}$ viene misurata come la probabilità di osservare lo stato del nodo target.
Criteri di Punteggio:
- Soglia di Probabilità ( $p^*$ ): Una soglia dinamica è definita per garantire che il successo sia significativamente migliore del semplice azzardo casuale. Per distanza $d \le 2$ , $p^* = 1/3$ . Per $d > 2$ , $p^* = 1/5 + 1/2^d$ .
- Metrica: La probabilità di successo è mediata su più batch (4 batch da 1000 shot) e su più istanze di nodi target (2 per i cicli, 4 per il torus).
- Punteggio QWS: Il punteggio è la dimensione massima del problema $(n, d)$ per la quale la probabilità di successo misurata supera $p^*$ prima del primo fallimento. Il punteggio è calcolato come $QWS_{cycle} = 2^{e_n-1} + e_d$ e $QWS_{torus} = 2^{e_n} + e_d$ , dove $(e_n, e_d)$ è l'ultima istanza di successo.

Contributi Chiave

Design del Protocollo: Introduzione di un protocollo di benchmark completo e orientato alle applicazioni che integra DTQW e AA, due routine critiche per i futuri algoritmi quantistici.
Scalabilità e Riproducibilità: Il protocollo è progettato per essere applicabile a qualsiasi computer quantistico basato su gate, con parametri sperimentali standardizzati (conteggi degli shot, batching) e parametri algoritmici flessibili ( $num\_w$ , $num\_aa$ ) lasciati all'utente finale per l'ottimizzazione.
Analisi Teorica ed Empirica: Il documento fornisce garanzie teoriche sull'esistenza di parametri che possono teoricamente risolvere qualsiasi dimensione del problema, insieme a una dettagliata stima delle risorse (scalabilità della profondità del circuito) sia per le implementazioni algoritmiche che per quelle hardware native.
Validazione Sperimentale: Il protocollo viene eseguito su tre generazioni di processori quantistici IBM (Heron r2, Heron r3 e Nighthawk r1), fornendo una valutazione proof-of-concept delle capacità dell'hardware attuale.

Risultati

Simulazioni Senza Rumore: Le simulazioni su un computer quantistico ideale dimostrano che il benchmark è risolvibile per grandi dimensioni del problema. Nello scenario "suff-perf" (minimizzazione delle iterazioni AA), le probabilità di successo rimangono vicine alla soglia. Nello scenario "best-perf", le probabilità di successo si avvicinano a 1, sebbene ciò richieda profondità di circuito più elevate.
Scalabilità della Profondità del Circuito: La profondità algoritmica teorica scala come $O(nd)$. Tuttavia, quando traspilata sull'architettura Heron di IBM, la profondità nativa scala come $O(n^{3.45}d)$ per i grafi ciclici e $O(n^{2.2}d)$ per i grafi torus 2D, evidenziando l'importante overhead della mappatura hardware.
Prestazioni Sperimentali su Hardware IBM:
- Gli esperimenti sul processore ibm_kingston (Heron r2) hanno mostrato che le probabilità di successo diminuiscono rapidamente all'aumentare della dimensione del problema a causa del rumore e della decoerenza.
- Il sistema ha superato con successo la soglia solo fino alla dimensione del problema (3, 1). La probabilità di successo è crollata a risultati simili a tentativi casuali per le dimensioni successive, con l'eccezione della dimensione del problema (4, 1), che non ha costituito una sequenza di successi continui. Di conseguenza, il Quantum WalkScore per i grafi ciclici è stato determinato come 5 nello scenario "suff-perf".
- Per istanze più grandi (ad esempio, profondità > 700 porte), i risultati sono degradati a livelli indistinguibili dal caso casuale.
- I confronti tra Heron r2, Heron r3 e Nighthawk r1 hanno mostrato tendenze simili, con Heron r3 che offriva un'accuratezza leggermente migliore, ma tutte le architetture attuali hanno faticato con circuiti che superano le ~1000 porte.

Significatività e Rivendicazioni
Il documento sostiene che il QWS serva come strumento necessario per colmare il divario tra le metriche astratte dell'hardware e le prestazioni delle applicazioni pratiche. Concentrandosi sul problema di ricerca del nodo nel grafo, esso valuta direttamente la capacità di un hardware di eseguire le essenziali primitive quantistiche (DTQW e AA) richieste per compiti di ottimizzazione e ricerca.

Gli autori sottolineano che il benchmark evidenzia l'interazione tra i parametri algoritmici e i limiti dell'hardware. I risultati dimostrano che, sebbene il framework teorico permetta di risolvere problemi di grandi dimensioni, i dispositivi NISQ attuali sono limitati dalla profondità del circuito e dall'accumulo di errori. Il documento conclude che il QWS fornisce un punteggio significativo e interpretabile per tracciare la maturazione dei computer quantistici, distinguendo le prestazioni tra i dispositivi NISQ e i futuri dispositivi di Calcolo Quantistico Tollerante ai Guasti (FTQC). Il modesto punteggio di 5 ottenuto sull'hardware attuale sottolinea le significative sfide tecnologiche che rimangono prima che questi algoritmi possano essere applicati a problemi pratici su larga scala.

Sintesi Tecnica: Quantum WalkScore (QWS)

Articoli simili