Gustav Schmid

We present the first \emph{local} problems that show a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently \emph{global} definition [Le Gall et al.\ 2019]. This submission consists of two works: \begin{itemize} \item The first work\footnote{{\bf Distributed Quantum Advantage for Local Problems} by Balliu, Brandt, Coiteux-Roy, d'Amore, Equi, Le Gall, Lievonen, Modanese, Olivetti, Renou, Suomela, Tendick and Veeren. \emph{Proceedings of the 57th ACM Symposium on Theory of Computing (STOC 2025)}, pp. 451-462, 2025.} presents a problem that we call \emph{iterated GHZ}, which is defined using only local constraints. We show that in graphs of maximum degree $\Delta$, any classical (deterministic or randomized) LOCAL model algorithm will require $\Omega(\Delta)$ rounds to solve the iterated GHZ problem, while the problem can be solved in $1$ round in quantum-LOCAL. \item The second work\footnote{{\bf Distributed Quantum Advantage in Locally Checkable Labeling Problems} by Balliu, Casagrande, d'Amore, Equi, Keller, Lievonen, Olivetti, Schmid and Suomela. arXiv:2504.05191, 2025.} shows the first known example of a local problem \emph{over a constant-degree graph} that admits asymptotic distributed quantum advantage in the LOCAL model of distributed computing: our problem can be solved in $O(\log n)$ communication rounds in the quantum-LOCAL model, but it requires $\Omega(\log n\cdot\log^{0.99}\log n)$ communication rounds in the classical randomized-LOCAL model. \end{itemize}

We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: beginenumerate ıtem We give a new distributed algorithm that finds a c-coloring in χ-chromatic graphs in tildemathcalO(n^frac1alpha) rounds, with alpha = biglłfloorfracc-1chi - 1bigrrfloor. ıtem We prove that any distributed algorithm for this problem requires Ømega(n^frac1alpha) rounds. endenumerate Our upper bound holds in the classical, deterministic mathsfLOCAL model, while the near-matching lower bound holds in the emphnon-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic mathsfLOCAL and randomized mathsfLOCAL but also mathsfquantum-mathsfLOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or c-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.