Il quantum annealing può risolvere i puzzle dei grafi? Scopriamolo!

Immagina di dover accoppiare il maggior numero possibile di amici a una festa, senza che nessuno abbia più di un compagno. Questo è il problema del "maximum cardinality matching" nei grafi, un classico rompicapo di matematica e informatica. Ora, pensa a un computer quantistico che, invece di provare tutte le combinazioni una alla volta, usa la fisica quantistica per “annealare” (raffreddare) il problema fino a trovare la soluzione migliore. Questo è il quantum annealing, una tecnica sviluppata da D‑Wave e altri.\n\nPer capire se il quantum annealing è davvero più veloce dei metodi tradizionali, gli scienziati hanno creato dei benchmark: una serie di istanze di matching di diverse dimensioni e complessità. Hanno poi confrontato i risultati ottenuti da un annealer quantistico con quelli di algoritmi classici su laptop e supercomputer.\n\nI risultati mostrano che, per grafi piccoli‑medi, il quantum annealer riesce a trovare soluzioni quasi ottimali in pochi microsecondi, mentre gli algoritmi classici impiegano più tempo. Tuttavia, quando i grafi diventano molto grandi, le limitazioni hardware (numero di qubit, rumore) fanno sì che le prestazioni quantistiche scendano.\n\nQuesta ricerca è importante perché dimostra dove la computazione quantistica può davvero fare la differenza e dove serve ancora migliorare la tecnologia. In futuro, con più qubit e meno rumore, potremmo vedere il quantum annealing diventare lo strumento preferito per risolvere problemi di matching e altri puzzle combinatori.

Il problema del maximum cardinality matching (MCM) è formalmente definito su un grafo G=(V,E) come la ricerca di un sottoinsieme M⊆E tale che nessun due archi di M condividano un vertice e |M| sia massimale. Classicamente, algoritmi polinomiali come l'algoritmo di Hopcroft‑Karp (O(√|V|·|E|) per grafi bipartiti) o l'algoritmo di Edmonds (O(|V|³) per grafi generali) risolvono il problema in tempo deterministico.\n\nIl quantum annealing (QA) sfrutta il principio di adiabaticità quantistica: il sistema è inizialmente preparato in uno stato fondamentale di un Hamiltoniano semplice H₀, poi evolve lentamente verso un Hamiltoniano finale H₁ che codifica il problema di ottimizzazione. La mappatura di MCM su QA richiede la traduzione del problema in un modello di Ising o QUBO (Quadratic Unconstrained Binary Optimization). In pratica, si introduce una variabile binaria xᵢⱼ per ogni arco (i,j)∈E, imponendo penalità quadratiche per violazioni di disgiunzione (due archi incidenti su uno stesso vertice) e premi per la massimizzazione del numero di archi selezionati. L'Hamiltoniano risultante è H= A·∑_{v∈V}(∑_{e∈δ(v)} x_e -1)² - B·∑_{e∈E} x_e, dove A≫B garantisce che le soluzioni ammissibili (matching) siano energeticamente preferite.\n\nNel benchmark, le istanze sono generate con grafi random (Erdős‑Rényi) e grafi strutturati (planari, bipartiti) di dimensioni da 10 a 200 nodi. Le metriche di performance includono il tempo di annealing (τ), la probabilità di trovare lo stato di energia minima (success probability) e la qualità della soluzione (gap rispetto all'ottimo). I risultati mostrano che per |V|≤50, QA su D‑Wave Advantage™ raggiunge success probability >0.9 con τ≈10µs, mentre gli algoritmi classici richiedono O(10⁻³‑10⁻² s). Per |V|>100, la densità di connessioni supera la topologia Chimera/ Pegasus, costringendo a embedding con catene di qubit, aumentando il rumore e riducendo la success probability a <0.3.\n\nLe limitazioni attuali derivano da: (i) numero finito di qubit (≈5000 su Advantage), (ii) connettività limitata che richiede embedding costosi, (iii) decoerenza e rumore termico che introducono errori di lettura. Prospettive future includono l'espansione a qubit più numerosi, architetture di connettività più densa (es. Pegasus), e tecniche di error correction adiabatiche. Inoltre, l'uso di hybrid quantum‑classical solvers (QAOA + QA) potrebbe migliorare la scalabilità per MCM su grafi molto grandi, combinando la rapidità quantistica per la ricerca locale con la robustezza classica per la verifica globale.