Meno qubit, scelte migliori: selezione di sub-QUBO consapevole degli accoppiamenti per il partizionamento delle zone di traffico assistito dalla computazione quantistica

Abstract degli autori

Gli ottimizzatori quantistici di breve termine possono gestire circa un centinaio di variabili binarie, perciò è necessario scomporre i grandi problemi di ottimizzazione binaria quadratica non vincolata in sottoproblemi delle dimensioni compatibili con l’hardware, mantenendo fisse le altre variabili. In genere, le variabili vengono selezionate classificando le variazioni della funzione obiettivo dovute a singoli flip. Mostriamo che questa regola non è informativa quando la soluzione corrente è ottimale rispetto ai flip di una singola variabile: ogni punteggio rappresenta un costo, mentre i miglioramenti residui dipendono da interazioni a coppie trascurate. Uno sviluppo del secondo ordine porta invece a un problema di selezione del sottografo più denso con raccolta di premi, risolvibile con un algoritmo greedy in un tempo lineare rispetto al numero di variabili, e a due limiti, calcolabili senza solver, che racchiudono il miglioramento ottenibile all’interno di un sottoinsieme selezionato. Nelle reti di trasporto di Chicago e Filadelfia, la nostra regola, con sottoproblemi da 16 variabili, supera la selezione casuale con sottoproblemi da 64 variabili, dimostrando che quadruplicare la capacità del dispositivo non compensa una selezione meno efficace. Sostituire l’adiacenza geometrica con la connettività della rete stradale amplia il margine di un fattore compreso tra 1,6 e 1,9. Mantenendo fissa la sequenza di selezione, variare da zero a uno la frazione di sottoproblemi risolti su un dispositivo da 120 qubit lascia invariata la funzione obiettivo finale a sei cifre significative. Alle dimensioni testate e accessibili all’hardware, i miglioramenti derivano quindi dalla selezione, non dal backend. La fattibilità su hardware è limitata dai termini di accoppiamento: problemi con 120 variabili non riescono a essere compilati con 7.260 termini, ma vengono compilati con 5.118. I tempi di compilazione crescono quasi quadraticamente rispetto al numero di termini e dominano i costi di esecuzione, arrivando a 1.752 secondi contro 469 secondi di elaborazione quantistica.