No distributed quantum advantage for approximate graph coloring

• URL: http://arxiv.org/abs/2307.09444v3
• Date: Fri, 22 Mar 2024 14:26:33 GMT
• Title: No distributed quantum advantage for approximate graph coloring
• Authors: Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela,
• Abstract summary: 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.
• Score: 2.8518543181146785
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give an almost complete characterization of the hardness of $c$-coloring $\chi$-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: 1) We give a new distributed algorithm that finds a $c$-coloring in $\chi$-chromatic graphs in $\tilde{\mathcal{O}}(n^{\frac{1}{\alpha}})$ rounds, with $\alpha = \bigl\lfloor\frac{c-1}{\chi - 1}\bigr\rfloor$. 2) We prove that any distributed algorithm for this problem requires $\Omega(n^{\frac{1}{\alpha}})$ rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-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 LOCAL and randomized LOCAL but also quantum-LOCAL, 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.

Related papers

• 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)
• 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)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• 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)
• Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
  We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability. The algorithms achieve a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. An existing framework for using distributed version of Grover's search algorithm to accelerate triangle finding lies at the core of the speedup.
  arXiv  Detail & Related papers  (2023-04-06T02:18:52Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model. It is assumed that the graph's structure is known and has $N$ nodes. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
  arXiv  Detail & Related papers  (2022-08-26T16:21:31Z)
• 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)
• 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)
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs [6.262125516926276]
  We show that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of $> 5$ a maximum cut of at most $1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$. We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$, where
  arXiv  Detail & Related papers  (2021-06-10T16:28:23Z)
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions [0.0]
  We show that $1D$ random quantum circuits have a spectral gap scaling as $Omega(n-1)$, provided that $t$ is small compared to the local dimension: $t2leq O(q)$. Our second result is an unconditional spectral gap bounded below by $Omega(n-1log-1(n) t-alpha(q))$ for random quantum circuits with all-to-all interactions.
  arXiv  Detail & Related papers  (2020-12-09T19:00:50Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

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.