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)$ 量子比特，表明经典预处理无法显著减少所需的量子通信量。据我们所知，这是双向混合通信复杂性中首个非平凡的经典与量子通信权衡结果。