Exponential Quantum Advantage for Message Complexity in Distributed Algorithms

• URL: http://arxiv.org/abs/2510.01657v1
• Date: Thu, 02 Oct 2025 04:28:54 GMT
• Title: Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
• Authors: François Le Gall, Maël Luce, Joseph Marchand, Mathieu Roget,
• Abstract summary: We show an exponential quantum advantage for a fundamental task: routing information between two specified nodes of a network.<n>Our quantum algorithm is based on the recent "succinct" implementation of quantum walks over the welded trees by Li, Li and Luo.
• Score: 0.8808021343665321
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate how much quantum distributed algorithms can outperform classical distributed algorithms with respect to the message complexity (the overall amount of communication used by the algorithm). Recently, Dufoulon, Magniez and Pandurangan (PODC 2025) have shown a polynomial quantum advantage for several tasks such as leader election and agreement. In this paper, we show an exponential quantum advantage for a fundamental task: routing information between two specified nodes of a network. We prove that for the family of ``welded trees" introduced in the seminal work by Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003), there exists a quantum distributed algorithm that transfers messages from the entrance of the graph to the exit with message complexity exponentially smaller than any classical algorithm. Our quantum algorithm is based on the recent "succinct" implementation of quantum walks over the welded trees by Li, Li and Luo (SODA 2024). Our classical lower bound is obtained by ``lifting'' the lower bound from Childs, Cleve, Deotto, Farhi, Gutmann and Spielman (STOC 2003) from query complexity to message complexity.

Related papers

• Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model [0.5074812070492739]
  We present new distributed quantum algorithms for fundamental distributed computing problems.<n>These problems include leader election, broadcast, Minimum Spanning Tree (MST), and Breadth-First Search (BFS) tree, in arbitrary networks.<n>The message complexity of our algorithms is $tildeO(n)$ for leader election, broadcast, and MST, and $tildeO(sqrtmn)$ for BFS.
  arXiv  Detail & Related papers  (2026-02-17T12:10:12Z)
• Coherence Fraction in Grover Search Algorithm [17.812164427695926]
  We show that entanglement and coherence do not fully explain the quantum advantage achieved by the Grover search algorithm.<n>We also explore the role of the coherence fraction in the quantum minimization algorithm.<n>These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.
  arXiv  Detail & Related papers  (2025-11-10T08:29:05Z)
• Quantum algorithms through graph composition [0.40792653193642503]
  We introduce the graph composition framework, a generalization of the st-connectivity framework for generating quantum algorithms.<n>We show how the st-connectivity framework subsumes the learning graph framework, the weighted-decision-tree framework, and a zero-error version of the latter.<n>We also simplify existing quantum algorithms for the space-efficient directed st-connectivity problem, the pattern-matching problem and the infix-search problem.
  arXiv  Detail & Related papers  (2025-04-02T20:20:51Z)
• Quantum Communication Advantage for Leader Election and Agreement [0.6937243101289334]
  We present and show how quantum algorithmic techniques such as Grover search, quantum counting, and quantum walks can make distributed algorithms significantly message-efficient.<n>In particular, our leader election protocol for diameter-2 networks uses quantum walks to achieve the improved message complexity.
  arXiv  Detail & Related papers  (2025-02-11T09:52:20Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware. We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth. We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
  arXiv  Detail & Related papers  (2023-05-17T18:00:06Z)
• Concise and Efficient Quantum Algorithms for Distribution Closeness Testing [0.2741266294612775]
  We study the impact of quantum computation on the fundamental problem of testing the property of distributions. We propose the currently best quantum algorithms for this problem under the metrics of $l1$-distance and $l2$-distance.
  arXiv  Detail & Related papers  (2023-02-13T04:03:59Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)

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.