2026-07-20T11:32:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26544 2026-07-01T07:16:14Z ddc:004 open_access

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity Wu, Xudong Yang, Guangxu Yao, Penghui Hybrid communication Generalized discrepancy bound Dual polynomial Query-to-communication lifting 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xudong Wu and Guangxu Yang and Penghui Yao 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.155 urn:nbn:de:0030-drops-265449 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.155 eng https://creativecommons.org/licenses/by/4.0/legalcode