Vai al contenuto
Quantum.world

The Signal

Secondo i ricercatori, il metodo QUBO senza variabili di slack per il problema dello zaino ottiene i risultati migliori

Un preprint confronta tre modi efficienti nell’uso delle risorse per formulare il problema dello zaino come QUBO, mettendoli alla prova in simulazioni LR-QAOA e su un dispositivo D-Wave per l’annealing quantistico. Tutti e tre aumentano la probabilità di trovare una soluzione ottimale, mentre il metodo senza variabili di slack produce incrementi di diversi ordini di grandezza anche per problemi relativamente piccoli.

Secondo i ricercatori, il metodo QUBO senza variabili di slack per il problema dello zaino ottiene i risultati migliori

Un preprint riferisce che tre modi efficienti nell’uso delle risorse per formulare il problema dello zaino come problema di ottimizzazione binaria quadratica senza vincoli aumentano la probabilità di trovare una soluzione ottimale. I ricercatori hanno messo alla prova gli approcci in simulazioni dell’algoritmo di ottimizzazione approssimata quantistica a rampa lineare, o LR-QAOA, e su un dispositivo D-Wave per l’annealing quantistico. Il metodo che evita le variabili di slack ha ottenuto i risultati migliori, con probabilità di successo aumentate, secondo quanto riportato, di diversi ordini di grandezza anche per problemi di dimensioni relativamente ridotte.

Fonte arxiv.org

Perché confrontare le formulazioni del problema dello zaino?

Gli approcci all’ottimizzazione quantistica operano di solito su problemi espressi come QUBO. Molti problemi di ottimizzazione possono essere riformulati in questa forma e uno stesso problema può avere più di una formulazione possibile. Gli autori scrivono: «La scelta della formulazione può influenzare notevolmente le prestazioni pratiche dei risolutori QUBO». Il loro studio esamina la questione usando il problema dello zaino, che descrivono come un esempio canonico di problema con vincoli di disuguaglianza.

L’articolo, “Resource-efficient formulations of the Knapsack problem for quantum computing,” è stato presentato ad arXiv il 4 novembre 2026. Gli autori sono Pim van den Heuvel, Vrinda Mehta, Dennis Willsch, J. A. Montanez-Barrera e Kristel Michielsen.

Tre approcci al QUBO

Nella formulazione standard descritta nell’abstract, i vincoli di disuguaglianza vengono convertiti in termini di penalità. Questo approccio richiede variabili di slack aggiuntive. I ricercatori esaminano tre alternative pensate per rendere la formulazione più efficiente nell’uso delle risorse, confrontandole con l’approccio standard attraverso i test sui risolutori riportati nello studio.

Le prime due alternative modificano la formulazione standard in modi diversi. Una ricava una costante di penalità più piccola; l’altra riduce il numero di variabili di slack. La terza segue una strada diversa ed elimina del tutto le variabili di slack. L’abstract presenta quest’ultimo approccio come un metodo completamente diverso, anziché come un’ulteriore modifica della formulazione standard.

Le prestazioni riportate

I ricercatori riferiscono che tutte e tre le alternative aumentano la probabilità di trovare la soluzione ottimale in entrambi i tipi di valutazione: le simulazioni LR-QAOA e i test su un dispositivo D-Wave per l’annealing quantistico. Lo studio indica invece che, tra i tre, il metodo senza variabili di slack ottiene i risultati migliori.

Per questo metodo, l’aumento riportato della probabilità di successo raggiunge diversi ordini di grandezza, anche per problemi di dimensioni relativamente ridotte. Il risultato riguarda la probabilità di trovare una soluzione ottimale nelle valutazioni descritte dagli autori.

Il confronto si concentra quindi su come le scelte nella codifica del problema dello zaino influenzino i risultati riportati per i risolutori QUBO. Secondo lo studio, sia la riduzione della costante di penalità sia quella del numero di variabili di slack sono vantaggiose, mentre l’eliminazione totale delle variabili di slack produce le prestazioni migliori tra quelle riportate.

Fonte

  1. arXiv

Notizie correlate

Esplora

Altri articoli