Quantum Advantage for Distributed Symmetry Breaking Avantage quantique pour briser la symétrie

Maxime Flin, Longcheng Li, Jukka Suomela

Theorem 1. There is a 4-round quantum-LOCAL algorithm that 3-colors directed cycles with high probability.

Théorème 1. Il existe un algorithme quantum-LOCAL en 4 rounds qui calcule une 3-coloration des cycles orientés avec forte probabilité.

Theorem 1 is obtained by first computing a 20,000-coloring of the directed cycle with a quantum algorithm, and then applying classical color reduction. The main result proven in the paper is the following:

Pour obtenir le théorème 1, on calcule d'abord une coloration du cycle orienté à 20000 couleurs à l'aide d'un algorithme quantique, puis on applique une technique de réduction de couleurs classique. Le résultat principal démontré dans l'article est le suivant:

Theorem 2. For all \(\varepsilon > 0\), there exists a one-way one-round anonymous quantum-LOCAL algorithm that \(2 \cdot 10^4\)-colors the directed cycle such that any given edge is monochromatic with probability at most \(\varepsilon\).

Théorème 2. Pour tout \(\varepsilon > 0\), il existe un algorithme quantum-LOCAL anonyme, unidirectionnel et en un round, qui calcule une \(2 \cdot 10^4\)-coloration du cycle orienté telle que toute arête donnée soit monochromatique avec une probabilité d'au plus \(\varepsilon\).

Notably, the number of qubits used by the algorithm depends on \(\varepsilon\), but the round complexity is independent of \(\varepsilon\). Our algorithm uses \(O(\log(1/\varepsilon))\) qubits, and this is optimal up to a constant factor. In the limit, one can get a zero-error one-way one-round quantum-LOCAL algorithm where each node uses infinitely many qubits.

Le nombre de qubits utilisés par l'algorithme dépend de \(\varepsilon\), mais pas son nombre de rounds. Notre algorithme utilise \(O(\log(1/\varepsilon))\) qubits, ce qui est optimal à un facteur constant près. En passant à la limite, on obtient un algorithme quantum-LOCAL unidirectionnel en un round et sans erreur dans lequel chaque nœud utilise une infinité de qubits.

See arXiv for the full proof.

La preuve complète est disponible sur arXiv.