A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

1. Problem Statement

The paper investigates the hybrid classical-quantum communication complexity model. In this model, two parties (Alice and Bob) communicate in two distinct stages:

1. Classical Phase: They exchange $c$ classical bits and perform local classical computations.
2. Quantum Phase: They subsequently exchange $q$ qubits and perform local quantum operations (with prior entanglement allowed).

The central research question is to characterize the trade-off between the classical communication cost ($c$) and the quantum communication cost ($q$). Specifically, the authors ask: Can classical pre-processing significantly reduce the quantum communication required to compute a composed function?

The authors focus on composed functions of the form $f \circ G^n$, where:

• $f: \{0, 1\}^n \to \{\pm 1\}$ is an outer function.
• $G: \Lambda \times \Lambda \to \{0, 1\}$ is an inner gadget function (specifically, the inner product function on $\Theta(\log n)$ bits).

2. Methodology

The core technical contribution is a novel lifting theorem that unifies two previously separate paradigms in communication complexity:

1. Classical Lifting: Query-to-communication lifting (translating decision tree depth to communication cost).
2. Quantum Lifting: Approximate-degree-to-generalized-discrepancy lifting (translating polynomial degree to quantum communication cost).

The methodology proceeds in three main steps:

A. The Hybrid Lifting Framework

The authors establish that if a hybrid protocol computes $f \circ G^n$ with costs $(c, q)$, there exists a deterministic decision tree of depth $O(c/b)$ (where $b$ is the gadget size) such that for any query outcome, the restricted outer function $f_{J,z}$ has an approximate degree of $O(q/b)$.

B. Handling Arbitrary Rectangles via "Density"

A major challenge in hybrid models is that the classical phase partitions the input space into arbitrary rectangles $R = U \times V$. Standard quantum lifting theorems (like those by Sherstov) often require specific structures or constant-sized gadgets.

• Innovation: The authors introduce a "density" condition for rectangles. A rectangle is "dense" if the distribution of inputs within it is sufficiently uniform (specifically, 0.99-dense in terms of min-entropy).
• Key Insight: They prove that even on these arbitrary dense rectangles, the Generalized Discrepancy Method can still be applied effectively. They construct a witness matrix $\Psi = \psi \circ G^n$ (where $\psi$ is a dual polynomial for $f$) and show that the spectral norm and inner product bounds hold, provided the gadget size $b = \Theta(\log n)$ is large enough.

C. Locating Dense Rectangles

To ensure the existence of a dense rectangle after the classical phase, the authors adapt the query-to-communication lifting technique (from works like GPW20, CFK+19):

• They construct a decision tree that simulates the classical communication.
• At each step, if the current rectangle is not dense, they "fix" a set of coordinates $I$ to restore density.
• They prove that the number of coordinates fixed is bounded by $O(c/b)$, ensuring that the remaining unqueried function still retains high complexity (high degree or block sensitivity).

3. Key Contributions

1. First Non-Trivial Trade-off Theorem: This is the first work to establish a non-trivial lower bound on the trade-off between classical and quantum communication in a two-way hybrid model.
2. Unified Lifting Theorem: The paper bridges the gap between classical combinatorial lifting (using gadgets) and quantum analytic lifting (using approximate degrees and discrepancy). It shows that these techniques can be combined to analyze hybrid protocols.
3. Density Property for Quantum Lifting: The authors identify that the "density" property, originally used for classical lifting, is the exact condition required to lift approximate degrees to quantum communication complexity on restricted domains.
4. Refutation of Classical Pre-processing: The results demonstrate that classical pre-processing cannot significantly reduce the quantum communication burden for composed functions.

4. Main Results

The paper proves the following lower bound for any hybrid protocol computing $f \circ G^n$ with error $\epsilon$:
$$c + q^2 = \Omega\left( \max\{\deg(f), \text{bs}(f)\} \cdot \log n \right)$$
Where:

• $\deg(f)$ is the polynomial degree of $f$.
• $\text{bs}(f)$ is the block sensitivity of $f$.
• $b = \Theta(\log n)$ is the gadget size.

Specific Implications for Read-Once Formulas:
For read-once formulas (where $\deg(f) = n$ and $\text{bs}(f) = n$), the trade-off becomes nearly tight:

• Either $c = \Omega(n \log n)$ (purely classical cost),
• Or $q = \Omega(\sqrt{n} \log n)$ (purely quantum cost).

This implies that if the parties try to reduce classical communication below $O(n \log n)$, the quantum communication cost does not drop below the standard quantum query complexity scaled by the gadget size. Classical pre-processing offers no "free lunch" for reducing quantum costs in this regime.

5. Significance

• Theoretical Advancement: It resolves a long-standing gap in understanding hybrid communication models. Prior to this, lower bounds for hybrid models were scarce because classical and quantum techniques were disjoint.
• NISQ Era Relevance: As the field moves toward the Noisy Intermediate-Scale Quantum (NISQ) era, where hybrid classical-quantum algorithms (like VQE and QAOA) are standard, understanding the fundamental limits of resource trade-offs is crucial. This work suggests that for certain hard problems, simply adding a classical pre-processing step will not drastically lower the quantum resource requirements.
• Methodological Impact: The "density" condition and the unified lifting framework provide new tools for researchers to prove lower bounds in other hybrid or restricted communication models.
• Open Problems: The paper opens several avenues for future research, including extending these results to randomized hybrid models, different gadget functions, and models where quantum communication precedes classical communication.

In summary, the paper provides a rigorous mathematical framework proving that for composed functions, the total communication cost in a hybrid model is fundamentally constrained by the complexity of the outer function, preventing significant savings by splitting the task between classical and quantum phases.