The Quantum Message Complexity of Distributed Wake-Up with Advice

• URL: http://arxiv.org/abs/2602.05801v1
• Date: Thu, 05 Feb 2026 15:55:42 GMT
• Title: The Quantum Message Complexity of Distributed Wake-Up with Advice
• Abstract summary: We present the first upper and lower bounds on the message complexity for wake-up in the quantum routing model.<n>We show that wake-up has a quantum message complexity of $( n3/2 )$ without advice, which holds independently of how much time we allow.
• Score: 0.2578242050187029
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the distributed wake-up problem with advice, where nodes are equipped with initial knowledge about the network at large. After the adversary awakens a subset of nodes, an oracle computes a bit string (``the advice'') for each node, and the goal is to wake up all sleeping nodes efficiently. We present the first upper and lower bounds on the message complexity for wake-up in the quantum routing model, introduced by Dufoulon, Magniez, and Pandurangan (PODC 2025). In more detail, we give a distributed advising scheme that, given $α$ bits of advice per node, wakes up all nodes with a message complexity of $O( \sqrt{\frac{n^3}{2^{\max\{\lfloor (α-1)/2 \rfloor},0\}}}\cdot\log n )$ with high probability. Our result breaks the $Ω( \frac{n^2}{2^α} )$ barrier known for the classical port numbering model in sufficiently dense graphs. To complement our algorithm, we give a lower bound on the message complexity for distributed quantum algorithms: By leveraging a lower bound result for the single-bit descriptor problem in the query complexity model, we show that wake-up has a quantum message complexity of $Ω( n^{3/2} )$ without advice, which holds independently of how much time we allow. In the setting where an adversary decides which nodes start the algorithm, most graph problems of interest implicitly require solving wake-up, and thus the same lower bound also holds for other fundamental problems such as single-source broadcast and spanning tree construction.

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)
• Distributed quantum algorithm for the dihedral hidden subgroup problem [2.3026482262928587]
  This paper proposes a distributed algorithm for the dihedral hidden subgroup problem.<n>By splitting the original function into multiple subfunctions, the algorithm significantly reduces the quantum circuit depth and qubit requirements for individual nodes.<n>Compared to the original algorithm, the distributed version not only reduces the influence of circuit depth and noise, but also improves the probability of measurement success.
  arXiv  Detail & Related papers  (2025-03-09T06:32:26Z)
• Asymptotic robustness of entanglement in noisy quantum networks and graph connectivity [46.44827993583994]
  We show that when the links are noisy two drastically different behaviors can occur regarding the global entanglement properties of the network. While in certain configurations the network displays genuine multipartite entanglement (GME) for any system size provided the noise level is below a certain threshold, in others GME is washed out if the system size is big enough for any fixed non-zero level of noise.
  arXiv  Detail & Related papers  (2024-11-19T15:01:50Z)
• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
  We solve the $k$-sparse parity problem with sign gradient descent (SGD) on two-layer fully-connected neural networks.<n>We show that this approach can efficiently solve the $k$-sparse parity problem on a $d$-dimensional hypercube.<n>We then demonstrate how a trained neural network with sign SGD can effectively approximate this good network, solving the $k$-parity problem with small statistical errors.
  arXiv  Detail & Related papers  (2024-04-18T17:57:53Z)
• Scalable network reconstruction in subquadratic time [0.0]
  We present a general algorithm applicable to a broad range of reconstruction problems that significantly outperforms this quadratic baseline. Our algorithm relies on a second neighbor search that produces the best edge candidates with high probability. We show that our algorithm achieves a performance that is many orders of magnitude faster than the quadratic baseline.
  arXiv  Detail & Related papers  (2024-01-02T19:00:13Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  Normalized-Cut (N-Cut) is a famous model of spectral clustering. Traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via $K$-means or spectral rotation. We propose a novel N-Cut solver based on the famous coordinate descent method.
  arXiv  Detail & Related papers  (2023-11-26T07:11:58Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• 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)
• A Framework for Distributed Quantum Queries in the CONGEST Model [0.0]
  We give a general framework for implementing quantum query algorithms in Quantum CONGEST. We generalize the protocol for the distributed Deutsch-Jozsa problem. We also give quantum speedups for the problems of cycle detection and computation.
  arXiv  Detail & Related papers  (2022-02-22T15:18:39Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNN is a universal framework to scale up any convolution-based GNNs using Vector Quantization (VQ) without compromising the performance. Our framework avoids the "neighbor explosion" problem of GNNs using quantized representations combined with a low-rank version of the graph convolution matrix.
  arXiv  Detail & Related papers  (2021-10-27T11:48:50Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  We show that a given suboptimality $epsilon0$ is achieved master/workers networks in $Omegabig. We then propose algorithms matching the lower bounds either types of networks (up to log-overs) We assess effectiveness of the proposed algorithms on a robust logistic regression problem.
  arXiv  Detail & Related papers  (2021-07-22T14:25:16Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
  This paper proposes a emphfully asynchronous scheme for the policy evaluation problem of distributed reinforcement learning (DisRL) over directed peer-to-peer networks. Without waiting for any other node of the network, each node can locally update its value function at any time by using (possibly delayed) information from its neighbors.
  arXiv  Detail & Related papers  (2020-03-01T08:12:08Z)

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.