Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model

• URL: http://arxiv.org/abs/2212.02768v1
• Date: Tue, 6 Dec 2022 05:39:50 GMT
• Title: Non-trivial lower bound for 3-coloring the ring in the quantum LOCAL model
• Abstract summary: We study distributed algorithms for coloring the ring that perform only a single round of one-way communication. The probability of any quantum single-round one-way distributed algorithm to output a proper $3$-coloring is exponentially small in $n$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the LOCAL model of distributed computing, where in a single round of communication each node can send to each of its neighbors a message of an arbitrary size. It is know that, classically, the round complexity of 3-coloring an $n$-node ring is $\Theta(\log^*\!n)$. In the case where communication is quantum, only trivial bounds were known: at least some communication must take place. We study distributed algorithms for coloring the ring that perform only a single round of one-way communication. Classically, such limited communication is already known to reduce the number of required colors from $\Theta(n)$, when there is no communication, to $\Theta(\log n)$. In this work, we show that the probability of any quantum single-round one-way distributed algorithm to output a proper $3$-coloring is exponentially small in $n$.

Related papers

• Distributed Quantum Property Testing with Quantum Carrier Pigeons [2.764897610820182]
  We introduce a framework for distributed quantum inference under communication constraints.<n>We focus on the fundamental problem of quantum state certification.<n>We show that the copy complexity of distributed state certification is $(fracd22n_q 2n_c/22)$.
  arXiv  Detail & Related papers  (2026-09-08T15:09:45Z)
• No Distributed Quantum Advantage for 3-Coloring Rooted Trees and 2-Coloring Even Cycles [0.7009487789080343]
  Recently, Coiteux-Royetal.(STOC 2024) showed that quantum resources do not help for 3-coloring textitunrooted trees.<n>We show that quantum algorithms cannot save even a single round over classical deterministic algorithms for 2-coloring even-length cycles.
  arXiv  Detail & Related papers  (2026-07-06T09:24:41Z)
• 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)
• Unbounded Quantum Advantage in Communication with Minimal Input Scaling [0.0]
  We show an it unbounded quantum advantage in relation reconstruction without public coins. We also highlight some applications of this task to semi-device-independent dimension witnessing and the detection of Mutually Unbiased Bases.
  arXiv  Detail & Related papers  (2023-05-17T16:58:05Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• 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)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  We develop a novel connection between discrepancy minimization and (quantum) communication complexity. We show that for every collection of symmetric $n times n$ $A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ there exist signs $x in pm 1n such that the maximum eigenvalue of $sum_i leq n x_i A_i$ is at most
  arXiv  Detail & Related papers  (2021-10-19T16:51:11Z)
• 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)
• DEED: A General Quantization Scheme for Communication Efficiency in Bits [14.274085532399098]
  In distributed optimization, a popular technique to reduce communication is quantization. We provide a general analysis framework for inexact descent that is applicable to quantization schemes. We also propose a quantization scheme Double. gradient and Error Diminishing (DEED)
  arXiv  Detail & Related papers  (2020-06-19T21:38:44Z)
• Communication memento: Memoryless communication complexity [5.88864611435337]
  We study the communication complexity of computing functions $F:0,1ntimes 0,1n rightarrow 0,1$ in the memoryless communication model.
  arXiv  Detail & Related papers  (2020-05-08T14:33:25Z)
• Bosonic quantum communication across arbitrarily high loss channels [68.58838842613457]
  A general attenuator $Phi_lambda, sigma$ is a bosonic quantum channel that acts by combining the input with a fixed environment state. We show that for any arbitrary value of $lambda>0$ there exists a suitable single-mode state $sigma(lambda)$. Our result holds even when we fix an energy constraint at the input of the channel, and implies that quantum communication at a constant rate is possible even in the limit of arbitrarily low transmissivity.
  arXiv  Detail & Related papers  (2020-03-19T16:50:11Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)
• Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets [15.078027648304115]
  We consider the problem of implementing two-party interactive quantum communication over noisy channels. For a noiseless qudit channel over a $mathrmpoly(n)$ size alphabet, our main result is a simulation method that fails with probability less than $2-Theta(nepsilon)$ We conjecture that it is optimal up to a constant factor in the $sqrtepsilon$ term.
  arXiv  Detail & Related papers  (2020-01-09T02:48:43Z)
• Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks [0.0]
  The computation of the diameter is one of the most central problems in distributed computation. We show a $tilde O(sqrtnD)$-round quantum distributed algorithm for exact diameter computation, where $D$ denotes the diameter. This shows a separation between the computational power of quantum and classical algorithms in the CONGEST model.
  arXiv  Detail & Related papers  (2018-04-09T11:24:24Z)

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.