PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Limits of Quantum Multiparty Simultaneous Communication

Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela

arXiv:2609.10289v1cs.CCquant-ph

TL;DR

This paper asks whether unentangled quantum SMP messages can simulate the coordination afforded by public randomness. It introduces the multiparty relation ICk,n and establishes quantum lower bounds and a separation that holds as the number of players grows.

  • Problem

    The paper asks whether unentangled quantum communication can efficiently simulate the coordination capabilities of classical shared randomness, and whether Index Coordination has a natural all-player extension.

    Source: §1 · p. 2

  • Method

    The authors introduce and analyze ICk,n, using an exact factorization result for unambiguous identification of product states among their proof approaches.

    Source: §5 · p. 15

  • Results

    The paper establishes polynomial quantum lower bounds and an exponential separation for every k(n) ≥ 2, with bound constants independent of k.

    Source: §5 · p. 15

  • Takeaways & Limitations

    For unambiguous ICk,n, quantum communication and classical private randomness both have complexity Θ(n^(1−1/k)); local quantum encodings with a joint referee measurement do not asymptotically reduce that cost.

    Source: §5 · p. 15

    A direct-product theorem for bounded-error mixed states is obstructed by SDP duality constraints across multiple tensor products.

    Source: §4.2 · p. 10

Abstract

from arXiv · show

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 $\Omega(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 $\Omega(n^{1-1/k})$ qubits in the unambiguous regime and $\Omega(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 $\Omega(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.

1 Introduction

The introduction asks whether unentangled quantum SMP messages can reproduce the coordination provided by public randomness, then presents ICk,n as an all-player extension of Index Coordination. It reports k-dependent quantum lower bounds in both error regimes against efficient public-coin protocols.

1 Introduction

  • The SMP model has k separated players send independent messages to a referee who evaluates a joint function or relation on their inputs.The introduction frames comparison among private randomness, public randomness, and unentangled quantum superposition.Source: §1 · p. 2
  • The introduction identifies the open gap as a natural Index Coordination extension involving every player, rather than adding dummy players to the two-party problem.The desired extension should grow harder for unentangled quantum protocols as the number of players increases.Source: §1 · p. 2

1.1 Our Contributions

  • For k ≥ c log n, both quantum lower bounds become Ω(n), matching the O(n) full-input protocol; constants independent of k extend the separation to every k(n) ≥ 2.The bounds' exponents increase with k and tend to one.Source: §1.1 · p. 3
  • In ICk,n, the first k−1 players each receive an n-bit string, and the kth receives an n-bit string plus a selector with exactly n/2 ones; the referee outputs a valid tuple at a selected coordinate.Source: §1.1 · p. 3
  • For IC_{k,n}, at least one player sends Ω(n^{1−1/k}) qubits in any unambiguous protocol; bounded-error protocols without shared randomness or prior entanglement require one player to send Ω(n^{(k−1)/(k+1)}) qubits.The comparison protocol is public-coin and O(log n), strictly unambiguous: it never errs and aborts with probability at most ε.Source: §1.1 · p. 4
  • The two lower-bound approaches use parity collapse for bounded error and a generalized unambiguous state-discrimination result for the unambiguous regime.Parity collapse groups the first k−1 players by input parity; the unambiguous approach uses a generalized direct-product theorem.Source: §1.1 · p. 4

2 Related Work

The related work positions this paper at the intersection of quantum communication complexity and quantum state discrimination. It distinguishes its relational, maximum-message analysis from prior multiparty results and from work using shared entanglement.

2 Related Work

  • The paper situates its contribution across quantum communication complexity and quantum state discrimination, building on earlier SMP milestones.Source: §2 · p. 4

Two-Party Separations

  • Two-party Index Coordination established that quantum communication without shared randomness cannot efficiently simulate public-coin coordination, using asymmetric state-identification bounds and random-access-code lemmas.The present bounded-error proof uses those two-register results as the endpoint of its parity-collapse reduction.Source: Two-Party Separations · p. 4

Multiparty Shared Randomness vs. Quantum Communication

  • Prior multiparty work on GPk used a trace-distance hybrid argument for total communication, whereas this work studies ICk,n and lower-bounds the maximum message through state identification and product structure.The reported maximum-message exponents are 1−1/k unambiguous and (k−1)/(k+1) bounded-error.Source: Multiparty Shared Randomness vs.… · p. 4

Multipartite Entanglement vs. Unentangled Messages

  • The cited entanglement-based protocols require prior shared multipartite entanglement, unlike this paper’s focus on unentangled messages.The comparison separates resource models rather than contradicting the unentangled-message lower bounds.Source: Multipartite Entanglement vs.… · p. 5

3 Preliminaries

This section establishes the quantum-information, communication-model, and information-theoretic tools used to prove multiparty separations. It culminates in a product bound for unambiguous identification of composite labels from product states.

3.1 Quantum Information Basics

  • Quantum states are density operators, measurements are POVMs, and trace distance quantifies how well two states can be distinguished.The section restricts attention to finite-dimensional Hilbert spaces.Source: §3.1 · p. 5

3.2 The (p, η)-Predictor and State Identification

  • A (p, η)-predictor guesses a uniformly distributed encoded bit, producing a conclusive answer with probability p and conditional error at most η.D_η is the supremum conclusive-answer probability over such measurements, capturing the trade-off between answer frequency and reliability.Source: §3.2 · pp. 5–6

3.3 Communication Models and Error Regimes

  • The multiparty SMP model has isolated players send one message each to an input-free referee, with communication measured by the longest message and protocols assessed in bounded-error or unambiguous regimes.Quantum messages are unentangled and use neither shared randomness nor prior entanglement; the error regimes differ in whether a conclusive answer may be incorrect.Source: §3.3 · p. 6

3.4 Information-Theoretic Tools

  • The Random Access Code lemma bounds the aggregate bit-prediction capacity extractable from one quantum encoding and applies in both unambiguous and bounded-error regimes.The proposition considers bit-specific measurements on an m-qubit encoding of a uniformly distributed string.Source: §3.4 · p. 7

3.5 The Direct-Product Theorem

  • For arbitrary finite alphabets, global unambiguous identification of a specific sequence from a product of mixed states succeeds with probability at most the product of the local success probabilities.The theorem derives this bound from a factorization of the global identification subspace into local exclusion subspaces.Source: §3.5 · pp. 7–8
  • The average-capacity corollary bounds global unambiguous success using each register’s optimal average symbol-identification probability under a uniform prior.The local measurement must be unambiguous for its entire ensemble.Source: §3.5 · p. 8

4 Exponential Separations for Multiparty Index Coordination

Multiparty Index Coordination (ICk,n) asks a referee to output the players’ bits at an index selected by the last player. The section contrasts efficient classical protocols with quantum message lower bounds in bounded-error and unambiguous regimes.

4.1 Classical Protocols for ICk,n

  • O(log n) bits suffice for an unambiguous public-coin protocol, which repeats random index sampling until it finds a valid index.Each trial samples a uniform index, valid with probability 1/2; repetition reduces the abort probability.Source: §4.1 · p. 9
  • A private-coin tensor-hyperplane protocol succeeds with probability at least 1/4 per trial, and every conclusive output is valid.For arbitrary n, each hyperplane contains at most 4n^(1-1/k) entries.Source: §4.1 · p. 10

4.2 Bounded-Error Quantum Lower Bound

  • Parity collapse reduces the bounded-error multiparty analysis to a two-register task, avoiding a direct product bound for k mixed states.The section notes that SDP duality constraints across multiple tensor products obstruct such a direct bound.Source: §4.2 · pp. 10–11
  • m=Ω(n^((k-1)/(k+1))) qubits are required for bounded-error quantum SMP protocols without shared randomness or prior entanglement.The proof groups the first k−1 players’ bits by parity and applies a two-register identification bound.Source: §4.2 · pp. 11–12

4.3 Unambiguous Strong Quantum Lower Bound

  • The unambiguous lower-bound constant depends only on the fixed abort allowance, not on n or k.The bounded-error proof likewise states that its implicit constant is independent of n and k.Source: §4.3 · p. 14, §4.2 · p. 14
  • m=Ω(n^(1-1/k)) qubits are required for unambiguous quantum SMP protocols without shared randomness or prior entanglement.The proof bounds tuple-identification success by the product of local capacities, then applies random-access-code bounds.Source: §4.3 · p. 14

5 Conclusion and Open Problems

The paper establishes multiparty quantum communication lower bounds for ICk,n and identifies open questions about bounded-error direct-product bounds and the gap between its two error regimes.

5 Conclusion and Open Problems

  • The unambiguous lower bound uses exact subspace factorization, while the bounded-error lower bound uses a structural parity-collapse technique.Parity collapse groups the first k − 1 players into one register to apply existing two-register asymmetric direct-product theorems.Source: §5 · p. 15, A Multiparty Direct Product Theorem… · p. 15
  • For fixed error parameters, constants independent of k establish the exponential separation for every integer-valued k(n) ≥ 2, including arbitrarily growing k.Both quantum lower bounds are Ω(n) when k ≥ c log n for any fixed c > 0, matching the O(n) full-input protocol in both regimes.Source: §5 · p. 15
  • ICk,n requires Ω(n^(1−1/k)) unambiguous quantum qubits and Ω(n^((k−1)/(k+1))) bounded-error qubits, versus O(log n) public-coin bits and Θ(n^(1−1/k)) private-coin unambiguous communication.The unambiguous private-coin upper bound matches the quantum lower bound.Source: §5 · p. 15

A Multiparty Direct Product Theorem for Bounded-Error Identification

  • A direct generalized direct-product theorem for identifying target sequences encoded across k-fold tensor products of mixed states in the bounded-error regime remains an open question.The proposed alternative is to bound identification probabilities directly for all k labels.Source: A Multiparty Direct Product Theorem… · p. 15

Unifying the Lower Bounds Across Error Regimes

  • For fixed k, whether the weaker bounded-error lower-bound exponent reflects problem complexity or a proof limitation remains unresolved.The two bounds arise from different RAC specializations: an L1 constraint in the unambiguous case and an L2 sum-of-squares constraint in the bounded-error case.Source: Unifying the Lower Bounds Across Error… · p. 16

A Proof of Theorem 1

The proof characterizes the global subspace that must be excluded for unambiguous identification, then uses its factorization into local orthogonal complements to bound success.

A Proof of Theorem 1

  • For target string b, the global wrong subspace Wb is the span of product subspaces indexed by every label string b′ ≠ b.Each such product subspace is a tensor product of local subspaces.Source: A Proof of Theorem 1 · p. 18
  • The orthogonal complement of Wb factorizes completely across the players’ tensor registers.This generalized subspace factorization holds for arbitrary k and finite alphabets under the lemma’s stated subspace assumptions.Source: A Proof of Theorem 1 · p. 18
  • Every incorrect label string differs from b in at least one coordinate, so the global wrong subspace can be expressed through local wrong subspaces embedded as cylinders.The proof computes the orthogonal complement of each cylinder and intersects those complements using commuting projectors on distinct tensor factors.Source: A Proof of Theorem 1 · pp. 18–19
  • Unambiguous success requires the referee’s measurement element for b to be orthogonal to every incorrect product-state support and hence to their span.The factorization then supplies the local orthogonal complements used in the global trace bound.Source: A Proof of Theorem 1 · pp. 19–20

B Proof of Theorem 3

The proof pools the first k − 1 players’ coordinate-wise unambiguous prediction capacities to select a hard subset, then bounds the referee’s valid-output probability using product-state identification.

B Proof of Theorem 3

  • For each coordinate, the first k − 1 players’ optimal unambiguous measurements act as predictors that answer correctly with probability a_j(i) and never return a wrong bit.The proof applies the RAC inequality to these predictors and aggregates their capacities.Source: B Proof of Theorem 3 · pp. 20–21
  • A subset S of n/2 coordinates can be chosen so each pooled capacity ci is at most 2M/n, where M is the first k − 1 players’ total communication budget.The proof obtains this threshold from Markov’s inequality; when M = 0, any subset of size n/2 works.Source: B Proof of Theorem 3 · p. 21
  • Conditioned on a coordinate and its input-bit tuple, independent inputs and product messages give the referee a product state whose measurement identifies that tuple unambiguously.The proof bounds the referee’s probability of a valid output by applying the product-state identification result and averaging over bit tuples.Source: B Proof of Theorem 3 · pp. 21–22
  • The proof combines the pooled capacity bound with the referee’s success sum, applies AM-GM to the first k − 1 players, and rearranges to an explicit message-size bound.The final asymptotic step uses M ≤ (k − 1)m and mk ≤ m.Source: B Proof of Theorem 3 · p. 22
Loading 2609.10289v1…