On the Limits of Quantum Multiparty Simultaneous Communication

• URL: http://arxiv.org/abs/2609.10289v1
• Date: Wed, 09 Sep 2026 15:07:22 GMT
• Title: On the Limits of Quantum Multiparty Simultaneous Communication
• Abstract summary: 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$.
• Score: 1.7205106391379026
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Simultaneous Message Passing (SMP) model provides a fundamental framework for comparing classical and quantum communication. For two players, Gavinsky et al. (STOC 2006) established a separation underlying the incomparability of shared randomness and quantum communication: \textsc{Index Coordination} needs $O(\log n)$ public-coin bits but $Ω(n^{1/3})$ bounded-error qubits. In this work, we establish a multiparty exponential separation through $\operatorname{IC}_{k,n}$, a natural $k$-party generalization of \textsc{Index Coordination}. Public-coin protocols solve it unambiguously with maximum message length $O(\log n)$ bits. In contrast, quantum SMP protocols without shared entanglement or public coins require maximum message length $Ω(n^{1-1/k})$ qubits in the unambiguous regime and $Ω(n^{(k-1)/(k+1)})$ qubits in the bounded-error regime. A classical private-coin protocol matches the unambiguous bound, so quantum communication provides no asymptotic advantage over private randomness in this regime. For fixed error parameters, all constants are independent of $k$, establishing the exponential separation for every integer-valued function $k=k(n)\ge2$, without restricting its growth. Both quantum lower bounds become $Ω(n)$ when $k\ge c\log n$ for any fixed $c>0$, matching the full-input protocol and yielding tight linear complexity in both regimes. Our results demonstrate that quantum superposition cannot efficiently simulate the coordination afforded by public randomness, extending this separation to arbitrary $k$. To bound success probabilities for multiparty product states, we prove an exact factorization theorem for unambiguous quantum state identification, which may be of independent mathematical interest.

Related papers

• Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication [0.0]
  We prove that the optimal worst-case communication per instance for $fn$ converges to [ Dparallel(f)=log|mathrmRow(f)|+log|mathrmCol(f)|.<n>We also prove that the same threshold governs an exponential strong converse.
  arXiv  Detail & Related papers  (2026-09-13T16:55:55Z)
• Distributed Quantum Property Testing with Quantum Carrier Pigeons [2.764897610820182]
  We introduce a framework for distributed quantum inference under communication constraints.<n>We focus on the fundamental problem of quantum state certification.<n>We show that the copy complexity of distributed state certification is $(fracd22n_q 2n_c/22)$.
  arXiv  Detail & Related papers  (2026-09-08T15:09:45Z)
• Quantum memory advantage for quantum process tomography [2.956729394666618]
  Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information.<n>We show that quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments.<n>Our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
  arXiv  Detail & Related papers  (2026-07-15T06:09:08Z)
• 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)
• Trade-offs between Entanglement and Communication [5.88864611435337]
  We show that quantum simultaneous protocols with $tildeTheta(k5 log3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known.
  arXiv  Detail & Related papers  (2023-06-02T01:49:39Z)
• 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)
• 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)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• 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)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• 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.