Ottimizzazione di Motzkin-Straus su una piattaforma di calcolo dell’entropia

Abstract degli autori

Presentiamo un framework per l’ottimizzazione combinatoria basato su programmi quadratici continui con vincolo sulla somma, risolvibili dal computer fotonico per il calcolo dell’entropia Dirac-3S di QCi. Ciò è reso possibile dal teorema di Motzkin-Straus, che costituisce un potente ponte tra i problemi discreti delle clique e l’ottimizzazione sul simplesso delle probabilità. Dimostriamo la versatilità di questo framework risolvendo problemi di soddisfacimento di vincoli e presentando benchmark estesi sulla suite DIMACS. La piattaforma Dirac-3S eguaglia o supera nettamente due baseline classiche implementate in modo indipendente in oltre quattro quinti delle istanze del benchmark, raggiungendo la migliore soluzione nota in quasi tutte le famiglie di grafi strutturati e superando persino entrambi i solutori classici in diverse tra le istanze più grandi testate. D’altra parte, gli ottimizzatori continui classici ben calibrati mantengono un vantaggio solo sulle istanze più difficili di clique piantata. Questo lavoro stabilisce una via praticabile per risolvere problemi di ottimizzazione combinatoria usando piattaforme di calcolo non convenzionale nativamente analogiche, e posiziona il calcolo dell’entropia come un approccio competitivo per esplorare paesaggi non convessi e fornire baseline rigorose per un paradigma computazionale emergente.