2025/11/21 by Wu, Xudong, Yang, Guangxu, Yao, Penghui
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2511.17227
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∘ Gn, where f:\0,1\n→\±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∘ Gn must satisfy c+q2=Ω(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 \widetildeΘ(√ 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.