Distributed Quantum Advantage in Locally Checkable Labeling Problems

• URL: http://arxiv.org/abs/2504.05191v1
• Date: Mon, 07 Apr 2025 15:42:05 GMT
• Title: Distributed Quantum Advantage in Locally Checkable Labeling Problems
• Authors: Alkida Balliu, Filippo Casagrande, Francesco d'Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, Jukka Suomela,
• Abstract summary: We present the first known example of a locally checkable labeling problem (LCL) that admits distributed quantum advantage in the LOCAL model distributed computing.<n>Our problem can be solved in $O(log n)$ communication rounds in the quantum- model, but it requires $Omega(log n)$ communication rounds in the classical model.
• Score: 1.4886567189108137
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we present the first known example of a locally checkable labeling problem (LCL) 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. We also show that distributed quantum advantage cannot be arbitrarily large: if an LCL problem can be solved in $T(n)$ rounds in the quantum-LOCAL model, it can also be solved in $\tilde O(\sqrt{n T(n)})$ rounds in the classical randomized-LOCAL model. In particular, a problem that is strictly global classically is also almost-global in quantum-LOCAL. Our second result also holds for $T(n)$-dependent probability distributions. As a corollary, if there exists a finitely dependent distribution over valid labelings of some LCL problem $\Pi$, then the same problem $\Pi$ can also be solved in $\tilde O(\sqrt{n})$ rounds in the classical randomized-LOCAL and deterministic-LOCAL models. That is, finitely dependent distributions cannot exist for global LCL problems.

Related papers

• Distributed Quantum Advantage for Local Problems [3.1024627815534593]
  We show a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. We present a problem that we call iterated GHZ, which is defined using only local constraints.
  arXiv  Detail & Related papers  (2024-11-05T16:38:49Z)
• Predicting quantum channels over general product distributions [19.09244195034539]
  We learn the mapping beginequation* rho mapsto mathrmTr(O E[rho]) endequation* to within a small error for most $rho$ sampled from a distribution $D$. We propose a new approach that achieves accurate prediction over essentially any product distribution $D$, provided it is not "classical" in which case there is a trivial exponential lower bound.
  arXiv  Detail & Related papers  (2024-09-05T16:39:13Z)
• Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
  We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC) By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity, leading to general theorems bounding the time complexity of a class of algorithms.
  arXiv  Detail & Related papers  (2024-06-06T11:33:29Z)
• Online Locality Meets Distributed Quantum Computing [2.3821076274208552]
  Three lines of research have recently explored extensions of the classical LOCAL model of distributed computing. We prove new results on the capabilities and limitations of all of these models, for locally checkable labeling problems (LCLs) Our work implies limitations on the advantage in the distributed setting, and we also exhibit a new barrier for proving tighter bounds.
  arXiv  Detail & Related papers  (2024-03-04T10:03:54Z)
• No distributed quantum advantage for approximate graph coloring [2.8518543181146785]
  We give an almost complete characterization of the hardness of $c$-coloring $chi$-chromatic graphs with distributed algorithms. We show that these problems do not admit any distributed quantum advantage.
  arXiv  Detail & Related papers  (2023-07-18T17:17:27Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.