Francois Le Gall

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}

In this work, we present new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarithm of the determinant of sparse, well-conditioned, positive matrices can be approximated to $\varepsilon$-relative accuracy in time polylogarithmic in the dimension~$N$, specifically in time~$\mathrm{poly}(\mathrm{log}(N), s, \kappa, 1/\varepsilon)$, where $s$ is the sparsity and $\kappa$ the condition number of the input matrix. We provide a simple dequantization of these techniques that preserves the polylogarithmic dependence on the dimension, at the cost of worse scaling in the sparsity, condition number, and accuracy. Our classical algorithm runs in time~$\mathrm{poly}\mathrm{log}(N)\cdot s^{O(\sqrt{\kappa}\log \kappa/\varepsilon)}$ which constitutes an exponential improvement over previous classical algorithms in certain parameter regimes. In addition, we prove $\mathsf{DQC}1$-completeness for estimating specific spectral sums such as the trace of the inverse and the trace of matrix powers with analogous parameter scalings as the quantum algorithms for the log-determinant in the case of log-local Hamiltonians. The latter solves a main open problem posed by Cade and Montanaro (TQC 2018) and is closely related to the complexity of Schatten $p$-norm estimation. It further shows that the parameter scalings of known quantum algorithms are not achievable classically, assuming~$\mathsf{BPP}\subsetneq\mathsf{DQC}1$. Further, we also consider a different input model where instead of a classical description of a sparse matrix, we are given a block-encoding of it and analyze the complexity of spectral sum estimation in this model. We obtain $\mathsf{DQC}1$-completeness of estimating $\mathrm{tr}[f(A)]$ in this model in a very general way, in particular whenever $f$ and $f^{-1}$ are Lipschitz continuous with bounded Lipschitz constants. We conclude our work with $\mathsf{BQP}$-hardness and $\mathsf{PP}$-completeness results on the estimation of the log-determinant.

In this work, we show that verifying the order of a finite group given as a black-box is in the complexity class QCMA. This solves an open problem asked by Watrous in 2000 in his seminal paper on quantum proofs and directly implies that the Group Non-Membership problem is also in the class QCMA, which further proves a conjecture proposed by Aaronson and Kuperberg in 2006. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box groups.

We extend the theory of locally checkable labeling problems (LCLs) from the classical LOCAL model to a number of other models that have been studied recently, including the quantum-LOCAL model, finitely-dependent processes, non-signaling model, dynamic-LOCAL model, and online-LOCAL model [e.g. STOC 2024, ICALP 2023]. First, we demonstrate the advantage that finitely-dependent processes have over the classical LOCAL model. We show that all LCL problems solvable with locality O(log⋆n) in the LOCAL model admit a finitely-dependent distribution (with constant locality). In particular, this gives a finitely-dependent coloring for regular trees, answering an open question by Holroyd [2023]. This also introduces a new formal barrier for understanding the distributed quantum advantage: it is not possible to exclude quantum advantage for any LCL in the Θ(log⋆n) complexity class by using non-signaling arguments. Second, we put limits on the capabilities of all of these models. To this end, we introduce a model called randomized online-LOCAL, which is strong enough to simulate e.g. SLOCAL and dynamic-LOCAL, and we show that it is also strong enough to simulate any non-signaling distribution and hence any quantum-LOCAL algorithm. We prove the following result for rooted trees: if we can solve an LCL problem with locality o(loglogn) in the randomized online-LOCAL model, we can solve it with locality O(log⋆n) in the classical deterministic LOCAL model. Put together, these results show that in rooted trees the set of LCLs that can be solved with locality O(log⋆n) is the same across all these models: classical deterministic and randomized LOCAL, quantum-LOCAL, non-signaling model, dynamic-LOCAL, and deterministic and randomized online-LOCAL.

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.

The generation and verification of quantum states are fundamental tasks for quantum information processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and Yuen [CCC 2022], Rosenthal and Yuen [ITCS 2022], Metger and Yuen [QIP 2023] under the term emphstate synthesis. This paper studies this concept from the viewpoint of quantum distributed computing, and especially distributed quantum Merlin-Arthur (dQMA) protocols. We first introduce a novel task, on a line, called state generation with distributed inputs (SGDI). In this task, the goal is to generate the quantum state Uketpsi at the rightmost node of the line, where ketpsi is a quantum state given at the leftmost node and U is an unitary matrix whose description is distributed over the nodes of the line. We give a dQMA protocol for SGDI and utilize this protocol to construct a dQMA protocol for the Set Equality problem studied by Naor, Parter and Yogev [SODA 2020], and complement our protocol by showing classical lower bounds for this problem. Our second contribution is a dQMA protocol, based on a recent work by Zhu and Hayashi [Physical Review A, 2019], to create EPR-pairs between adjacent nodes of a network without quantum communication. As an application of this dQMA protocol, we prove a general result showing how to convert any dQMA protocol on an arbitrary network into another dQMA protocol where the verification stage does not require any quantum communication.

Abstract This paper tackles the issue of checking that all copies of a large data set replicated at several nodes of a network are identical. The fact that the replicas may be located at distant nodes prevents the system from verifying their equality locally, i.e., by having each node consult only nodes in its vicinity. On the other hand, it remains possible to assign certificates to the nodes, so that verifying the consistency of the replicas can be achieved locally. However, we show that, as the replicated data is large, classical certification mechanisms, including distributed Merlin-Arthur protocols, cannot guarantee good completeness and soundness simultaneously, unless they use very large certificates. The main result of this paper is a distributed quantum Merlin-Arthur protocol enabling the nodes to collectively check the consistency of the replicas, based on small certificates, and in a single round of message exchange between neighbors, with short messages. In particular, the certificate-size is logarithmic in the size of the data set, which gives an exponential advantage over classical certification mechanisms. We propose yet another usage of a fundamental quantum primitive, called the SWAP test, in order to show our main result.