Un algoritmo euristico variazionale per MaxCut efficiente in qubit

Perché i piccoli chip quantistici sono importanti per grandi puzzle

Molti compiti del mondo reale — dalla disposizione dei circuiti elettronici alla modellizzazione dei materiali — si riducono a separare una rete in due gruppi tagliando il maggior numero possibile di connessioni tra loro. Questa sfida, nota come MaxCut, è notoriamente difficile per i computer classici. L’articolo presenta un nuovo metodo ispirato al mondo quantistico che può gestire reti sorprendentemente grandi usando soltanto una manciata di bit quantistici (qubit), offrendo un nuovo modo per testare e migliorare strumenti di ottimizzazione sia quantistici sia classici.

Dividere una rete in due metà utili

MaxCut pone una domanda dall’apparenza semplice: se si dispone di un insieme di punti (nodi) collegati da linee (archi), come bisogna colorare ogni nodo, per esempio blu o bianco, in modo che il maggior numero possibile di archi colleghi nodi di colori diversi? La migliore divisione possibile è preziosa in ambiti come il progetto di circuiti e la fisica statistica, ma è molto difficile da trovare esattamente quando la rete è grande. Un approccio classico ampiamente usato, l’algoritmo di Goemans–Williamson (GW), effettua una rilassazione intelligente del problema ed è garantito trovare un taglio che sia almeno circa l’88% del valore ottimale. Il calcolo quantistico promette nuovi modi per affrontare questi problemi, ma i dispositivi attuali sono rumorosi e di dimensioni limitate, rendendo difficile eseguire circuiti ampi e profondi.

Risolvere grafi grandi con pochi qubit

Gli approcci quantistici standard come il Quantum Approximate Optimization Algorithm (QAOA) richiedono un qubit per nodo della rete, quindi un grafo da 1.000 nodi richiederebbe 1.000 qubit — ben oltre le capacità delle macchine odierne. Il nuovo metodo, chiamato Qubit-Efficient MaxCut (QEMC), capovolge questa scala: usa soltanto circa il logaritmo del numero di nodi, il che significa che 11 qubit possono codificare informazioni su più di 2.000 nodi. Invece di legare ogni qubit a un singolo nodo, QEMC usa l’intero stato quantistico come uno spazio di indirizzamento compatto e fa corrispondere nodi diversi a stati di base differenti di questo piccolo registro. Questa parsimonia di qubit mantiene i circuiti poco profondi e più facili da eseguire su hardware rumoroso, pur rappresentando grafi molto grandi.

Colorare i nodi tramite probabilità invece che stati fissi

L’innovazione chiave è il modo in cui QEMC codifica il “colore” di ogni nodo. Invece di costringere ogni nodo a essere esattamente blu o bianco in un singolo stato quantistico, il metodo lascia che il colore di ciascun nodo sia dedotto da quanto è probabile osservarlo in una misura. Un nodo il cui stato di base appare con bassa probabilità è trattato come un colore; un nodo con probabilità più alta è trattato come l’altro. Un valore di soglia separa i due regimi. Ciò implica che molti stati quantistici diversi corrispondono essenzialmente allo stesso partizionamento del grafo. La funzione di costo che QEMC minimizza è costruita in modo che i nodi connessi siano incoraggiati a cadere su lati opposti di questa soglia di probabilità, il che tende ad aumentare il numero di archi che attraversano i due gruppi di colore e quindi migliora il taglio.

Testare le prestazioni su macchine reali e simulate

Gli autori testano QEMC su due fronti: processori quantistici reali e simulazioni classiche dei circuiti quantistici. Su piccoli grafi regolari fino a 32 nodi (usando solo 2–5 qubit), QEMC eseguito su hardware a superconduttore IBM trova tagli che eguagliano o si avvicinano molto alle risposte migliori ottenute per ricerca esaustiva, superando nettamente il caso casuale e studi quantistici precedenti basati su QAOA. Nelle simulazioni senza rumore, QEMC raggiunge costantemente oltre il 97% del taglio ottimale per questi piccoli grafi. Il vantaggio della codifica diventa ancora più evidente per grafi più grandi: per grafi 9-regolari fino a 2.048 nodi, le simulazioni classiche di QEMC superano ancora GW sia in media sia sul miglior taglio di qualche punto percentuale, e vantaggi simili si osservano su grafi casuali da 128 nodi con differenti densità.

Velocità, limiti e promessa ispirata al quantistico

Nonostante il successo, QEMC non fornisce ancora un vero vantaggio di velocità quantistica. Poiché usa solo circa log N qubit, la simulazione classica dei suoi circuiti scala anch’essa approssimativamente in modo lineare con il numero di nodi, e il tempo necessario per valutare la funzione di costo cresce con il numero di archi. Studi empirici suggeriscono che il tempo totale per raggiungere prestazioni al livello di GW cresce circa quadraticamente con la dimensione del grafo, il che è comunque alla portata pratica per molti problemi. Questo significa che QEMC, nella sua forma attuale, funziona più come un potente euristico ispirato al quantistico che come una dimostrazione di supremazia quantistica.

Cosa significa questo lavoro per il futuro

Per un non specialista, il messaggio principale è che dispositivi quantistici piccoli e rumorosi possono comunque essere utili scientificamente se progettiamo algoritmi che sfruttino i loro punti di forza. Codificando i colori dei nodi in intervalli di probabilità flessibili invece che in valori di bit rigidi, QEMC usa pochissimi qubit per affrontare problemi di rete molto grandi e tollera in modo naturale il rumore dell’hardware. Il metodo stabilisce un nuovo punto di riferimento per testare algoritmi di ottimizzazione quantistica e fornisce anche un algoritmo classico pratico basato sulle stesse idee. Più in generale, dimostra come ripensare la codifica dell’informazione — invece di limitarsi a costruire macchine più grandi — possa aprire vie promettenti per risolvere problemi computazionali difficili.

Citazione: Tene-Cohen, Y., Kelman, T., Lev, O. et al. A Variational Qubit-Efficient MaxCut Heuristic Algorithm. npj Quantum Inf 12, 50 (2026). https://doi.org/10.1038/s41534-026-01186-2

Parole chiave: MaxCut, ottimizzazione quantistica, algoritmi variazionali, partizionamento di grafi, calcolo ispirato al quantistico