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\circ G^n$, where $f:\{0,1\}^n\to\{\pm1\}$ 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\circ G^n$ must satisfy $c+q^2=Ω\big(\max\{\mathrm{deg}(f),\mathrm{bs}(f)\}\cdot\log n\big)$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{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 $Θ\big(n\cdot\log n\big)$ classical bits or $\widetildeΘ\big(\sqrt n\cdot\log n\big)$ 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.

翻译：我们研究了一种混合经典-量子通信复杂性模型，其中两方首先交换经典消息，随后使用量子消息进行通信。我们针对形式为 $f\circ G^n$ 的复合函数（其中 $f:\{0,1\}^n\to\{\pm1\}$，$G$ 是 $Θ(\log n)$ 比特的内积函数）研究了经典与量子通信之间的权衡关系。为证明该权衡关系，我们为混合通信复杂性建立了一个新颖的提升定理。该定理统一了先前分离的两个提升范式：经典通信复杂性的查询-通信提升框架，以及量子通信复杂性的近似度-广义差异提升方法。因此，我们的混合提升定理为证明混合经典-量子通信模型中的下界提供了一个新框架。作为推论，我们证明任何通过先传输 $c$ 比特经典信息再传输 $q$ 量子比特来计算 $f\circ G^n$ 的混合协议必须满足 $c+q^2=Ω\big(\max\{\mathrm{deg}(f),\mathrm{bs}(f)\}\cdot\log n\big)$，其中 $\mathrm{deg}(f)$ 是 $f$ 的度数，$\mathrm{bs}(f)$ 是 $f$ 的块敏感度。对于单次读取公式 $f$，这产生了一个近乎紧致的权衡：要么双方需要交换 $Θ\big(n\cdot\log n\big)$ 比特的经典信息，要么需要交换 $\widetildeΘ\big(\sqrt n\cdot\log n\big)$ 量子比特，这表明经典预处理无法显著减少所需的量子通信。据我们所知，这是双向混合通信复杂性中经典与量子通信之间首个非平凡的权衡关系。