Adaptive Dynamics and Its Applications to Chaos and NPC Problem Quantum Algorithm for SAT Problem and Quantum Mutual Entropy New Quantum Algorithm for Studying NP-Complete Problems Entanglement, Quantum Entropy and Mutual Information Fundamentals of Quantum Mutual Entropy and Capacity Compound Channels, Transition Expectations, and Liftings Complexities and Their Applications to Characterization of Chaos Complexity, Fractal Dimension for Quantum States Information Dynamics and Its Applications to Optical Communication Processes Information Theoretical Treatments of Genes Some Aspects of Quantum Information Theory and Their Applications to Irreversible Processes On Compound State and Mutual Information in Quantum Information Theory Note on Quantum Probability Quantum Ergodic Channels in Operator Algebras On Open System Dynamics -- An Operator Algebraic Study Dynamical Process in Linear Response Theory Stability of Weiss Ising Model and other papers.Adaptive Dynamics and Its Applications to Chaos and NPC Problem Quantum Algorithm for SAT Problem and Quantum Mutual Entropy New Quantum Algorithm for Studying NP-Complete Problems Entanglement, Quantum Entropy and Mutual Information Fundamentals of Quantum Mutual Entropy and Capacity Compound Channels, Transition Expectations, and Liftings Complexities and Their Applications to Characterization of Chaos Complexity, Fractal Dimension for Quantum States Information Dynamics and Its Applications to Optical Communication Processes Information Theoretical Treatments of Genes Some Aspects of Quantum Information Theory and Their Applications to Irreversible Processes On Compound State and Mutual Information in Quantum Information Theory Note on Quantum Probability Quantum Ergodic Channels in Operator Algebras On Open System Dynamics -- An Operator Algebraic Study Dynamical Process in Linear Response Theory Stability of Weiss Ising Model and other papers.

WORLD SCIENTIFIC eBooksFeb 1, 20080 citations

Lifting Theory and its Application to Quantum Amplifier Processes

Sh. Furuichi, K. Oshima, I. Hofuku

De Gruyter eBooksDec 31, 19990 citations

Optimal Optical Communication

Science NewsMay 2, 19810 citations

Some quantum problems in optical communications

Laura M. Morato

Alta FrequenzaFeb 1, 19770 citations

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

Xudong Wu, Guangxu Yang, Penghui Yao

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.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.

cs.CCCross-listedarXiv:2511.17227Leibniz international proceedings in informaticsNov 24, 20250 citations

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.