A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Guangxu Yang; Penghui Yao; Xudong Wu

arxiv: 2511.17227 · v3 · submitted 2025-11-21 · 💻 cs.CC · quant-ph

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Xudong Wu , Guangxu Yang , Penghui Yao This is my paper

Pith reviewed 2026-05-17 07:07 UTC · model grok-4.3

classification 💻 cs.CC quant-ph

keywords hybrid communication complexitylifting theoremclassical-quantum trade-offcomposed functionsinner product gadgetdegree and block sensitivityread-once formulas

0 comments

The pith

A lifting theorem shows hybrid protocols computing composed functions must satisfy c plus q squared equals Omega of max degree or block sensitivity times log n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a lifting theorem for hybrid classical-quantum communication complexity that combines the classical query-to-communication lifting approach with quantum approximate-degree-to-generalized-discrepancy methods. This unified theorem yields a concrete trade-off for protocols that first send c classical bits and then q qubits when computing functions of the form f composed with n copies of an inner-product gadget G on Theta log n bits. A sympathetic reader would care because the result gives the first explicit non-trivial bound showing that initial classical messages fail to meaningfully cut the quantum communication required, with nearly tight numbers for read-once formulas.

Core claim

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. As a corollary we show that any hybrid protocol communicating c classical bits followed by q qubits to compute f composed with G to the n must satisfy c plus q squared equals Omega of max of deg f and bs f times log n. For read-once formula f this yields an almost tight trade-off either Theta of n times log n classical bits or tilde Theta of square root n times log n.

What carries the argument

The hybrid lifting theorem, which reduces query measures such as degree and block sensitivity to a combined classical-plus-quantum communication cost via an inner-product gadget on the composed function f o G to the n.

If this is right

Any hybrid protocol for f o G to the n incurs total cost c plus q squared at least Omega of max{deg f, bs f} times log n.
Read-once formulas force a nearly tight choice between Theta n log n classical bits or tilde Theta square root n log n qubits.
Initial classical exchange cannot substantially lower the quantum communication that follows for these composed functions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same lifting approach may apply to other gadgets or to one-way hybrid models without two-way interaction.
This trade-off structure could guide lower-bound proofs for hybrid protocols in multi-party settings or for additional complexity measures such as sensitivity.

Load-bearing premise

The unification of the two prior lifting frameworks works only for the chosen inner-product gadget G of Theta log n bits together with the specific composed structure f o G to the n; if that choice breaks the unification the trade-off bound does not hold.

What would settle it

An explicit hybrid protocol for a read-once f o G to the n that communicates o of n log n classical bits followed by o of square root n log n qubits would falsify the claimed trade-off.

Figures

Figures reproduced from arXiv: 2511.17227 by Guangxu Yang, Penghui Yao, Xudong Wu.

**Figure 1.** Figure 1: An illustration of valid w1w2 ∈ Λ (A1⊎B1)∪(A2⊎C2) × Λ (A1⊎C1)∪(A2⊎B2) . The coordinates outlined by the thick black line are those of w1w2. A valid w1w2 satisfies: (w1)A1∪A2 = (w2)A1∪A2 , (w1)B1∪C2 = 0, and (w2)C1∪B2 = 0. The coordinates outlined by the blue line require that w1 and w2 be identical. So on the coordinates within the yellow and green area, w1w2 must be all 0. On the coordinates in the blue a… view at source ↗

read the original abstract

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 $\Theta(\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=\Omega\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 $\Theta\big(n\cdot\log n\big)$ classical bits or $\widetilde\Theta\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a hybrid lifting theorem that merges classical query lifting with quantum approximate-degree methods and derives a concrete c + q² trade-off for composed functions, though the classical-first messages raise a correlation issue worth checking in the proof.

read the letter

The paper's main contribution is a lifting theorem for hybrid classical-quantum communication complexity. It unifies the classical query-to-communication lifting with the quantum approximate-degree-to-generalized-discrepancy approach, and uses that to prove a lower bound on the sum of classical bits c and the square of qubits q for computing composed functions f composed with n copies of an inner-product gadget. What stands out is the corollary for read-once formulas. It shows that any hybrid protocol needs either Theta(n log n) classical bits or tilde Theta(sqrt(n) log n) qubits. This suggests that sending classical messages first does not let you cut the quantum communication by much. That is a clean result in a model that has not seen many trade-off theorems before. The unification itself is the new part. Previous work handled pure classical or pure quantum cases separately, and this tries to bridge them for the hybrid setting where classical comes before quantum. On the soft spots, the stress-test raises a fair point about whether the classical messages can create correlations across the n coordinates. Because the model sends all classical communication first, those messages could in principle carry joint information about several inputs to the gadget copies. For the lifting to go through, the proof has to show that you can still decompose the protocol into a query algorithm on f and then a quantum protocol on the residual function without the correlations breaking the independence. The manuscript does include a decomposition argument, but it would help to see more detail on how they bound any cross terms that the classical part might introduce. It is not obviously fatal, but it is the part that needs the most careful reading. This paper is aimed at people who work on communication complexity lower bounds, especially those interested in quantum and hybrid models. Someone following lifting theorems or discrepancy methods would find the framework worth looking at. It is not a complete resolution of hybrid complexity, but it adds a tool that could be applied elsewhere. I would bring it to a reading group to discuss the lifting construction. It is not something I would cite in my own work right away, but the bound for read-once functions is specific enough that it might get referenced in follow-up papers on hybrid models. It deserves peer review. The claim is concrete, the approach builds on established techniques, and the potential gap around correlations is something referees can check against the full proof. Recommendation: send it to referees with a note to verify the handling of classical message correlations in the decomposition step.

Referee Report

2 major / 2 minor

Summary. The manuscript establishes a lifting theorem for hybrid classical-quantum communication complexity that unifies classical query-to-communication lifting with quantum approximate-degree-to-generalized-discrepancy lifting. For functions of the form f ∘ G^n with G an inner-product gadget on Θ(log n) bits, it derives the lower bound c + q² = Ω(max{deg(f), bs(f)} ⋅ log n) on the classical bits c and qubits q communicated in a hybrid protocol. As a corollary for read-once formulas, it shows an almost tight trade-off where either Θ(n log n) classical bits or ~Θ(√n log n) qubits are required.

Significance. If the lifting theorem holds, this provides the first non-trivial trade-off between classical and quantum communication in the hybrid two-way model. It shows that classical pre-processing cannot substantially reduce the quantum communication needed for certain composed functions and offers a unified framework for lower bounds without free parameters or data fitting. The result strengthens the toolkit for hybrid communication complexity and yields concrete, falsifiable bounds for read-once formulas.

major comments (2)

[§4] §4 (Proof of the hybrid lifting theorem): The decomposition of a hybrid protocol (all classical messages first, followed by quantum messages) into a classical query algorithm on f and a residual quantum protocol on the composed function must explicitly address cross-coordinate correlations. Classical messages can transmit joint information about multiple coordinates of the input to G^n, potentially violating the product-structure assumption needed to apply the quantum lifting independently to each copy. Clarify how the analysis bounds or eliminates such leakage so that the claimed c + q² lower bound follows from the individual classical and quantum liftings.
[Corollary 1] Corollary 1 and the read-once formula application: The almost-tight trade-off claim (Θ(n log n) classical or ~Θ(√n log n) qubits) relies on the lifting theorem applying without additional logarithmic factors or looseness when f is read-once. Verify that the max{deg(f), bs(f)} term remains Ω(n) for the chosen read-once formulas and that the gadget size Θ(log n) does not introduce hidden dependencies that weaken the bound.

minor comments (2)

[Abstract] Abstract: 'We investigates' is a grammatical error; change to 'We investigate'.
[Introduction] Ensure bs(f) (block sensitivity) and deg(f) are defined at first use in the introduction or preliminaries, and confirm the inner-product gadget G is fully specified (input length and output range).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below with clarifications on the proof structure and parameter choices.

read point-by-point responses

Referee: [§4] §4 (Proof of the hybrid lifting theorem): The decomposition of a hybrid protocol (all classical messages first, followed by quantum messages) into a classical query algorithm on f and a residual quantum protocol on the composed function must explicitly address cross-coordinate correlations. Classical messages can transmit joint information about multiple coordinates of the input to G^n, potentially violating the product-structure assumption needed to apply the quantum lifting independently to each copy. Clarify how the analysis bounds or eliminates such leakage so that the claimed c + q² lower bound follows from the individual classical and quantum liftings.

Authors: In Section 4 the proof first applies the classical lifting theorem to the initial classical communication phase of c bits, reducing it to a query algorithm for f. To handle cross-coordinate correlations, the total classical communication bounds the mutual information between the transcript and any collection of input coordinates. This limits joint leakage, so that the residual quantum protocol operates on a distribution whose coordinate-wise marginals are close to independent (with total variation distance controlled by c). The quantum approximate-degree lifting is then applied to this effective instance, producing the q² term. The combined bound c + q² follows directly. We will add an explicit lemma formalizing the correlation bound in the revised version. revision: yes
Referee: [Corollary 1] Corollary 1 and the read-once formula application: The almost-tight trade-off claim (Θ(n log n) classical or ~Θ(√n log n) qubits) relies on the lifting theorem applying without additional logarithmic factors or looseness when f is read-once. Verify that the max{deg(f), bs(f)} term remains Ω(n) for the chosen read-once formulas and that the gadget size Θ(log n) does not introduce hidden dependencies that weaken the bound.

Authors: The read-once formulas used for Corollary 1 include the n-bit AND function, for which deg(f) = n and bs(f) = n, so max{deg(f), bs(f)} = Ω(n). The inner-product gadget of size Θ(log n) is the standard parameter from both the classical query-to-communication and quantum approximate-degree liftings; it produces precisely the multiplicative log n factor with no additional looseness or hidden dependencies. The claimed trade-off therefore holds as stated. We will insert a short verification sentence confirming these parameters. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained mathematical construction

full rationale

The paper presents a lifting theorem that unifies classical query-to-communication and quantum approximate-degree-to-generalized-discrepancy paradigms for hybrid protocols on f ∘ G^n. The central result and corollary bound are derived from the explicit construction of the hybrid lifting theorem and the properties of the inner-product gadget, without any reduction of predictions to fitted parameters, self-definitional equivalences, or load-bearing self-citations that collapse the argument. The proof decomposes protocols using the composed structure, and the trade-off follows directly from the theorem rather than being presupposed by inputs or prior author results invoked as axioms. This is a standard non-circular mathematical derivation in communication complexity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard background results from classical and quantum communication complexity together with the assumption that the inner-product gadget G behaves appropriately under composition; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Standard lifting theorems from classical query complexity and quantum approximate degree carry over to the hybrid classical-then-quantum setting when the gadget is inner product.
Invoked to unify the two prior paradigms and obtain the concrete bound.

pith-pipeline@v0.9.0 · 5610 in / 1272 out tokens · 45375 ms · 2026-05-17T07:07:59.723587+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages · 1 internal anchor

[1]

One clean qubit suffices for quantum communication advantage

[AGL23] Srinivasan Arunachalam, Uma Girish, and Noam Lifshitz. One clean qubit suffices for quantum communication advantage. CoRR, abs/2310.02406,

work page arXiv
[2]

Oracle separations of hybrid quantum-classical circuits

[AGS22] Atul Singh Arora, Alexandru Gheorghiu, and Uttam Singh. Oracle separations of hybrid quantum-classical circuits. CoRR, abs/2201.01904,

work page arXiv
[3]

Classical verification of quantum depth

[CH22] Nai-Hui Chia and Shih-Han Hung. Classical verification of quantum depth. CoRR, abs/2205.04656,

work page arXiv
[4]

Childs, Shelby Kimmel, and Robin Kothari

[CKK12] Andrew M. Childs, Shelby Kimmel, and Robin Kothari. The quantum query complexity of read-many formulas. In Algorithms – ESA 2012, Proceedings of the 20th Annual European Symposium, volume 7501, pages 337–348. Springer Berlin Heidelberg,

work page 2012
[5]

A Quantum Approximate Optimization Algorithm

[FGG14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate opti- mization algorithm. CoRR, abs/1411.4028,

work page internal anchor Pith review Pith/arXiv arXiv
[6]

Fourier spectrum of noisy quantum algorithms

[Gir25] Uma Girish. Fourier spectrum of noisy quantum algorithms. CoRR, abs/2510.06385,

work page arXiv
[7]

Simultaneous communication pro- tocols with quantum and classical messages

[GRdW08] Dmitry Gavinsky, Oded Regev, and Ronald de Wolf. Simultaneous communication pro- tocols with quantum and classical messages. Chicago Journal of Theoretical Computer Science, 2008,

work page 2008
[8]

The space just above one clean qubit

[JM24] Dale Jacobs and Saeed Mehraban. The space just above one clean qubit. CoRR, abs/2410.08051,

work page arXiv
[9]

Sherstov

[She11] Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing , 40(6):1969–2000,

work page 1969
[10]

Hybrid decision trees: Longer quantum time is strictly more powerful

[SZ19] Xiaoming Sun and Yufan Zheng. Hybrid decision trees: Longer quantum time is strictly more powerful. CoRR, abs/1911.13091,

work page arXiv 1911
[11]

Quantum versus classical separation in simultane- ous number-on-forehead communication

[YZ25] Guangxu Yang and Jiapeng Zhang. Quantum versus classical separation in simultane- ous number-on-forehead communication. CoRR, abs/2506.16804,

work page arXiv

[1] [1]

One clean qubit suffices for quantum communication advantage

[AGL23] Srinivasan Arunachalam, Uma Girish, and Noam Lifshitz. One clean qubit suffices for quantum communication advantage. CoRR, abs/2310.02406,

work page arXiv

[2] [2]

Oracle separations of hybrid quantum-classical circuits

[AGS22] Atul Singh Arora, Alexandru Gheorghiu, and Uttam Singh. Oracle separations of hybrid quantum-classical circuits. CoRR, abs/2201.01904,

work page arXiv

[3] [3]

Classical verification of quantum depth

[CH22] Nai-Hui Chia and Shih-Han Hung. Classical verification of quantum depth. CoRR, abs/2205.04656,

work page arXiv

[4] [4]

Childs, Shelby Kimmel, and Robin Kothari

[CKK12] Andrew M. Childs, Shelby Kimmel, and Robin Kothari. The quantum query complexity of read-many formulas. In Algorithms – ESA 2012, Proceedings of the 20th Annual European Symposium, volume 7501, pages 337–348. Springer Berlin Heidelberg,

work page 2012

[5] [5]

A Quantum Approximate Optimization Algorithm

[FGG14] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate opti- mization algorithm. CoRR, abs/1411.4028,

work page internal anchor Pith review Pith/arXiv arXiv

[6] [6]

Fourier spectrum of noisy quantum algorithms

[Gir25] Uma Girish. Fourier spectrum of noisy quantum algorithms. CoRR, abs/2510.06385,

work page arXiv

[7] [7]

Simultaneous communication pro- tocols with quantum and classical messages

[GRdW08] Dmitry Gavinsky, Oded Regev, and Ronald de Wolf. Simultaneous communication pro- tocols with quantum and classical messages. Chicago Journal of Theoretical Computer Science, 2008,

work page 2008

[8] [8]

The space just above one clean qubit

[JM24] Dale Jacobs and Saeed Mehraban. The space just above one clean qubit. CoRR, abs/2410.08051,

work page arXiv

[9] [9]

Sherstov

[She11] Alexander A. Sherstov. The pattern matrix method. SIAM Journal on Computing , 40(6):1969–2000,

work page 1969

[10] [10]

Hybrid decision trees: Longer quantum time is strictly more powerful

[SZ19] Xiaoming Sun and Yufan Zheng. Hybrid decision trees: Longer quantum time is strictly more powerful. CoRR, abs/1911.13091,

work page arXiv 1911

[11] [11]

Quantum versus classical separation in simultane- ous number-on-forehead communication

[YZ25] Guangxu Yang and Jiapeng Zhang. Quantum versus classical separation in simultane- ous number-on-forehead communication. CoRR, abs/2506.16804,

work page arXiv