Vantaggio quantistico nella rottura distribuita della simmetria

Abstract degli autori

Presentiamo un algoritmo quantistico distribuito che colora i cicli con $3$ colori in $O(1)$ round, con alta probabilità. Ne consegue che tutti i problemi di etichettatura verificabile localmente (LCL) che nel modello classico LOCAL hanno una complessità in round pari a $O(\log^* n)$ possono essere risolti in $O(1)$ round nel modello quantum-LOCAL, con alta probabilità; tra questi vi sono problemi come l’insieme indipendente massimale e il matching massimale nei grafi a grado limitato. Si tratta dei primi esempi naturali di problemi sui grafi che presentano un vantaggio quantistico distribuito asintotico nel modello LOCAL; tutti gli esempi precedenti che distinguono LOCAL e quantum-LOCAL sono problemi artificiali, costruiti soltanto per dimostrare il vantaggio quantistico.