Improved Separations between Quantum and Classical Communication Complexity of Total Functions

• URL: http://arxiv.org/abs/2609.16726v1
• Date: Tue, 15 Sep 2026 06:56:34 GMT
• Title: Improved Separations between Quantum and Classical Communication Complexity of Total Functions
• Abstract summary: We refine Gavinsky's framework for exponential separations between quantum and randomized communication complexity of total functions.<n>$ randomized communication with two quantum messages, and versus $(n1-varepsilon)$ for every fixed $0varepsilon1$ with more quantum messages.
• Score: 1.3706331473063882
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We refine Gavinsky's framework (arXiv:2608.18784) for exponential separations between quantum and randomized communication complexity of total functions and obtain larger separations: polylogarithmic quantum communication versus $\tildeΩ(\sqrt n)$ randomized communication with two quantum messages, and versus $Ω(n^{1-\varepsilon})$ for every fixed $0<\varepsilon<1$ with more quantum messages.

Related papers

• On the Limits of Quantum Multiparty Simultaneous Communication [1.7205106391379026]
  We establish a multiparty exponential separation through $nameIC_k,n$, a natural $k$-party generalization of textscIndex Coordination.<n>We show that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$.
  arXiv  Detail & Related papers  (2026-09-09T15:07:22Z)
• Constant-round quantum advantage in communication complexity for total functions [1.1602089225841632]
  We show that there exists a total function for which there is a gap between the randomized and the constant-round quantum communication complexity.<n>Previously, such separation was known only for quantum protocols usingly many rounds.
  arXiv  Detail & Related papers  (2026-08-20T08:32:27Z)
• On the quantum communication complexity of total functions [0.0]
  We present a total function with a polylogarithmic two-message quantum protocol, whereas every randomised protocol, even with arbitrarily many rounds, requires communication.
  arXiv  Detail & Related papers  (2026-08-19T10:42:51Z)
• Space-Bounded Communication Complexity of Unitaries [7.120902966697645]
  We study space-bounded communication complexity for unitary implementation in distributed quantum processors.<n>For general $n$-qubit unitaries, we improve upon the trivial $O(4n)$ communication bound.<n>For special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity.
  arXiv  Detail & Related papers  (2025-11-06T10:35:28Z)
• Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement [0.3004066195320147]
  We present relation problems whose input size is $n$ such that they can be solved with no communication for entanglement-assisted quantum communication models.<n>This is the maximum separation of quantum communication complexity with and without shared entanglement.
  arXiv  Detail & Related papers  (2025-05-22T09:41:04Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Bounds on oblivious multiparty quantum communication complexity [0.0]
  We show, for a wide class of functions, how to prove strong lower bounds on their oblivious quantum $k$-party communication complexity. In particular, we obtain an optimal $Omega(ksqrtn)$ lower bound on the oblivious quantum $k$-party communication complexity of the $n$-bit Set-Disjointness function.
  arXiv  Detail & Related papers  (2022-10-27T13:09:51Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Fault-tolerant Coding for Quantum Communication [71.206200318454]
  encode and decode circuits to reliably send messages over many uses of a noisy channel. For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable. Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
  arXiv  Detail & Related papers  (2020-09-15T15:10:50Z)
• 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)
• Quantum Statistical Complexity Measure as a Signalling of Correlation Transitions [55.41644538483948]
  We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signalling function of quantum order-disorder transitions. We apply our measure to two exactly solvable Hamiltonian models, namely: the $1D$-Quantum Ising Model and the Heisenberg XXZ spin-$1/2$ chain. We also compute this measure for one-qubit and two-qubit reduced states for the considered models, and analyse its behaviour across its quantum phase transitions for finite system sizes as well as in the thermodynamic limit by using Bethe ansatz.
  arXiv  Detail & Related papers  (2020-02-05T00:45:21Z)

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.