Algoritmi locali classici e quantistici con garanzie dimostrabili per Max-$k$-Cut e vantaggio quantistico a circonferenza moderata

Abstract degli autori

È stato dimostrato che ampliare lo studio degli algoritmi di ottimizzazione quantistica dagli alfabeti binari a quelli con $k$ elementi apre nuove possibilità per un potenziale vantaggio quantistico. Per sostenere una tesi di vantaggio quantistico nell’ottimizzazione approssimata, occorre dimostrare che, a parità di ipotesi, un algoritmo quantistico efficiente ottiene prestazioni migliori di quelle che si possono dimostrare per i migliori algoritmi classici efficienti noti. Studiamo algoritmi locali classici e quantistici per Max-$k$-Cut su grafi $d$-regolari di circonferenza $g$. Miglioriamo gli algoritmi classici per questo problema sviluppando un algoritmo locale basato su vettori, che utilizza la costruzione esplicita di vettori di Thompson, Parekh e Marwaha (TPM). Il nostro algoritmo offre la migliore garanzia dimostrabile sulla frazione di taglio tra quelle degli algoritmi classici efficienti noti per i grafi regolari con $k\geq3$. Per valutare le prestazioni di QAOA a parità di ipotesi di circonferenza e regolarità, sviluppiamo tecniche basate su reti tensoriali per valori generali di $d$ e $k \geq 2$. Inoltre, sfruttando l’equivalenza con un sistema accoppiato qudit--bosone, calcoliamo le prestazioni di QAOA nel limite di grado infinito. Nel complesso, queste tecniche forniscono garanzie dimostrabili sulle prestazioni di QAOA su grafi grandi. Nonostante i miglioramenti che introduciamo nell’algoritmo classico, QAOA offre una garanzia migliore sulla frazione di taglio per profondità $p\geq 9$, corrispondenti a una circonferenza $g\geq 20$, sia nel regime di grado finito sia in quello di grado infinito. Otteniamo così un apparente vantaggio quantistico applicando QAOA al problema Max-$k$-Cut.