A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity

• URL: http://arxiv.org/abs/2511.17227v1
• Date: Fri, 21 Nov 2025 13:14:04 GMT
• Title: A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
• Authors: Xudong Wu, Guangxu Yang, Penghui Yao,
• Abstract summary: We study the trade-off between the classical and quantum communication for composed functions of the form $f:0,1ntopm1$ and $G$.<n>We show that any hybrid protocol communicating $c$ classical bits followed by $q$ qubits must satisfy $c+q2=big.<n>This is the first non-trivial trade-off between classical and quantum communication in hybrid two-way communication complexity.
• Score: 10.42638550548464
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $Θ(\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.

Related papers

• Magic and communication complexity [0.6533091401094101]
  We establish novel connections between magic in quantum circuits and communication complexity.<n>We show that functions computable with low magic have low communication cost.
  arXiv  Detail & Related papers  (2025-10-08T17:14:25Z)
• Comparing classical and quantum conditional disclosure of secrets [0.0]
  conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in cryptography.<n>We study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in cryptography.
  arXiv  Detail & Related papers  (2025-05-05T18:14:18Z)
• One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
  We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer.
  arXiv  Detail & Related papers  (2023-10-03T19:58:08Z)
• Unbounded Quantum Advantage in Communication with Minimal Input Scaling [0.0]
  We show an it unbounded quantum advantage in relation reconstruction without public coins.<n>We also highlight some applications of this task to semi-device-independent dimension witnessing and the detection of Mutually Unbiased Bases.
  arXiv  Detail & Related papers  (2023-05-17T16:58:05Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  We consider a multi-party computation problem with $n$ players, where players $2, dots, n$ need to communicate appropriate information to player 1. We exhibit a quantum protocol (with complexity $(n-1) log n$ bits) and a classical protocol (with complexity $(n-1)2 (log n2$) bits) This demonstrates that our quantum protocol is strictly better than classical protocols.
  arXiv  Detail & Related papers  (2023-05-08T03:10:08Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Quantum teleportation in the commuting operator framework [63.69764116066747]
  We present unbiased teleportation schemes for relative commutants $N'cap M$ of a large class of finite-index inclusions $Nsubseteq M$ of tracial von Neumann algebras. We show that any tight teleportation scheme for $N$ necessarily arises from an orthonormal unitary Pimsner-Popa basis of $M_n(mathbbC)$ over $N'$.
  arXiv  Detail & Related papers  (2022-08-02T00:20:46Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.