Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography

Technical Summary: Exponential Advantage of Multipartite Entanglement over Quantum Communication

Problem Statement
While bipartite quantum entanglement is known to provide exponential advantages in communication complexity, the computational power of multipartite entanglement in distributed tasks remains less understood. This paper investigates whether multipartite entanglement can enable exponential communication savings in a setting involving multiple spatially separated senders and a single receiver. Specifically, the authors address the gap in understanding how genuinely multipartite correlations (which cannot be reduced to collections of bipartite correlations) compare to unrestricted quantum communication when no preshared entanglement is available.

Methodology
The authors introduce a multipartite communication task called Multipartite Hidden Matching ($mHM_n$) and its Boolean decision variant, Multipartite Boolean Hidden Matching ($mBHM_n$).

• Task Setup: There are $m$ senders (Alices), each receiving an input string $x_r \in \{0, 1\}^n$, and a receiver (Bob) who receives a perfect matching $M$ (or a partial $1/4$-matching for the Boolean version) on the set $[n]$.
• Goal: Bob must output an edge $(i_\ell, j_\ell)$ from $M$ along with the global parity of the corresponding bits across all senders: $\bigoplus_{r=1}^m (x_{r, i_\ell} \oplus x_{r, j_\ell})$.
• Models Compared: The study compares communication complexity under various resource models:
  1. Classical communication with preshared genuine multipartite entanglement (GHZ states).
  2. Unrestricted quantum communication without preshared entanglement.
  3. Classical communication with shared randomness.
• Analytical Tools:
  • Upper Bound Construction: A protocol utilizing an $(m+1)$-partite GHZ state. Senders apply local unitary phase encodings based on their inputs and measure in the Fourier basis, sending classical outcomes to Bob.
  • Lower Bound Proofs: The authors adapt and extend techniques from bipartite Hidden Matching lower bounds. For the unentangled quantum case, they employ a hypercontractive inequality for matrix-valued functions (generalizing the Kahn-Kalai-Linial inequality) to analyze the distinguishability of the output distribution from uniform.

Key Contributions and Results

1. Exponential Separation in Communication Complexity:

   • With Multipartite Entanglement: The authors demonstrate that if the senders and receiver share a GHZ state, the task can be solved with $O(\log n)$ bits of classical communication from each sender. The protocol exploits multipartite phase correlations to encode local inputs and recover the global parity at the receiver.
   • Without Preshared Entanglement: In contrast, any protocol achieving high success probability without preshared entanglement requires $\Omega(\sqrt{n})$ qubits of communication from at least one sender, even if unrestricted quantum communication is allowed.
   • Result: This establishes an exponential separation between classical communication assisted by multipartite entanglement and unassisted quantum communication. Notably, the lower bound holds even when senders share bipartite entanglement with the receiver, provided they do not share genuine multipartite entanglement among themselves.

2. Application to Bounded-Storage Cryptography:

   • The authors construct a seeded two-source randomness extractor based on the multipartite Hidden Matching problem. This extractor takes two independent weak random sources and a public seed (a matching) to produce a near-uniform output.
   • Security Against Unentangled Adversaries: The extractor is secure against adversaries possessing unentangled quantum side-information, provided the memory size is polynomial in $\sqrt{n}$.
   • Vulnerability to Entangled Adversaries: If the adversary possesses a small amount of preshared entanglement (specifically, $O(\log n)$ qubits of entangled memory per source), the extractor can be compromised.
   • Result: This establishes an exponential separation between the power of entangled versus unentangled quantum side-information. Compromising the extractor requires polynomial-size unentangled memory but only exponentially smaller entangled memory.

Significance and Claims
The paper claims to identify multipartite entanglement as a strictly stronger information-processing resource than quantum communication alone.

• Communication Regime: The work demonstrates that preshared GHZ entanglement is not merely a substitute for quantum communication but enables exponential savings that unrestricted quantum channels cannot achieve without such resources.
• Cryptographic Regime: The findings illuminate a qualitative distinction in bounded-storage cryptography: security against unentangled quantum adversaries does not necessarily extend to adversaries with even a modest amount of preshared entanglement.
• Scope: The authors position their cryptographic construction as a "proof-of-principle" rather than an optimized extractor, intended primarily to demonstrate the fundamental separation between entangled and unentangled side-information.

The paper concludes that multipartite entanglement should be regarded as a distinct computational resource whose power extends beyond the generation of nonlocal correlations, opening new directions for investigating distributed computational tasks and secure quantum networks.