DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.155

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Authors: Xudong Wu, Guangxu Yang, and Penghui Yao

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We investigates a model of hybrid classical-quantum communication complexity, in which two parties first exchange classical messages and subsequently communicate using quantum messages. We study the trade-off between the classical and quantum communication for composed functions of the form f∘Gⁿ, where f:{0,1}ⁿ → {±1} and G is an inner product function of Θ(log n) bits. To prove the trade-off, we establish a novel lifting theorem for hybrid communication complexity. This theorem unifies two previously separate lifting paradigms: the query-to-communication lifting framework for classical communication complexity and the approximate-degree-to-generalized-discrepancy lifting methods for quantum communication complexity. Our hybrid lifting theorem therefore offers a new framework for proving lower bounds in hybrid classical-quantum communication models. As a corollary, we show that any hybrid protocol communicating c classical bits followed by q qubits to compute f∘Gⁿ must satisfy c+q² = Ω(max{deg(f), bs(f)}⋅log n), where deg(f) is the degree of f and {bs}(f) is the block sensitivity of f. For read-once formula f, this yields an almost tight trade-off: either they have to exchange Θ(n⋅log n) classical bits or Θ(√n ⋅ log n) qubits, showing that classical pre-processing cannot significantly reduce the quantum communication required. To the best of our knowledge, this is the first non-trivial trade-off between classical and quantum communication in hybrid two-way communication complexity.

Cite as

Xudong Wu, Guangxu Yang, and Penghui Yao. A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 155:1-155:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wu_et_al:LIPIcs.ICALP.2026.155,
  author =	{Wu, Xudong and Yang, Guangxu and Yao, Penghui},
  title =	{{A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{155:1--155:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.155},
  URN =		{urn:nbn:de:0030-drops-265449},
  doi =		{10.4230/LIPIcs.ICALP.2026.155},
  annote =	{Keywords: Hybrid communication, Generalized discrepancy bound, Dual polynomial, Query-to-communication lifting}
}

Document

DOI: 10.4230/LIPIcs.DISC.2024.4

Almost Optimal Algorithms for Token Collision in Anonymous Networks

Authors: Sirui Bai, Xinyu Fu, Xudong Wu, Penghui Yao, and Chaodong Zheng

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

In distributed systems, situations often arise where some nodes each holds a collection of tokens, and all nodes collectively need to determine whether all tokens are distinct. For example, if each token represents a logged-in user, the problem corresponds to checking whether there are duplicate logins. Similarly, if each token represents a data object or a timestamp, the problem corresponds to checking whether there are conflicting operations in distributed databases. In distributed computing theory, unique identifiers generation is also related to this problem: each node generates one token, which is its identifier, then a verification phase is needed to ensure that all identifiers are unique. In this paper, we formalize and initiate the study of token collision. In this problem, a collection of k tokens, each represented by some length-L bit string, are distributed to n nodes of an anonymous CONGEST network in an arbitrary manner. The nodes need to determine whether there are tokens with an identical value. We present near optimal deterministic algorithms for the token collision problem with Õ(D+k⋅L/log n) round complexity, where D denotes the network diameter. Besides high efficiency, the prior knowledge required by our algorithms is also limited. For completeness, we further present a near optimal randomized algorithm for token collision.

Cite as

Sirui Bai, Xinyu Fu, Xudong Wu, Penghui Yao, and Chaodong Zheng. Almost Optimal Algorithms for Token Collision in Anonymous Networks. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.DISC.2024.4,
  author =	{Bai, Sirui and Fu, Xinyu and Wu, Xudong and Yao, Penghui and Zheng, Chaodong},
  title =	{{Almost Optimal Algorithms for Token Collision in Anonymous Networks}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.4},
  URN =		{urn:nbn:de:0030-drops-212319},
  doi =		{10.4230/LIPIcs.DISC.2024.4},
  annote =	{Keywords: Token collision, anonymous networks, deterministic algorithms}
}

Search Results

Documents authored by Wu, Xudong

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Abstract

Cite as

Almost Optimal Algorithms for Token Collision in Anonymous Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message