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 the communication advantages of bipartite quantum entanglement are well-established, the computational power of multipartite entanglement in distributed information processing remains less understood. A central open question is whether multipartite entanglement alone can provide exponential advantages in communication tasks comparable to those seen in bipartite settings. Specifically, the paper investigates whether classical communication assisted by multipartite entanglement can outperform unrestricted quantum communication that lacks preshared entanglement.

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

• Setup: The task involves $m$ spatially separated senders (Alices) and a single receiver (Bob). Each Alice receives an input string $x_r \in \{0, 1\}^n$. Bob receives a matching $M$ (a set of disjoint pairs from $\{1, \dots, n\}$).
• Goal: Bob must output a triple $(i_\ell, j_\ell, \bigoplus_{r=1}^m (x_r^{i_\ell} \oplus x_r^{j_\ell}))$ for some edge $(i_\ell, j_\ell) \in M$. In the Boolean variant, Bob must determine a specific bit $b$ based on a promise regarding the parity of the inputs across the matching.
• Models Compared: The authors analyze the communication complexity under several models:
  1. Classical communication with shared global randomness ($C_{\parallel, GSR}$).
  2. Classical communication assisted by genuine multipartite entanglement ($C_{\parallel, GEnt}$).
  3. Quantum communication without preshared entanglement ($Q_{\parallel, GSR}$).
  4. Quantum communication with bipartite entanglement between senders and receiver.

Key Contributions and Results

1. Exponential Advantage with Multipartite Entanglement:
   The authors demonstrate that if all parties share a Greenberger–Horne–Zeilinger (GHZ) state, the $mHM_n$ and $mBHM_n$ tasks can be solved with $O(\log n)$ bits of classical communication from each sender.

   • Mechanism: The senders apply local unitary phase encodings based on their inputs to their share of the GHZ state. They then measure in the Fourier basis and send the logarithmic-sized outcomes to Bob. Bob performs a specific unitary correction and measurement to deterministically recover the required global parity.
   • Remark: This protocol is "oblivious" in the sense that Bob learns only the global parity of the inputs across the matching edge, gaining no information about the individual inputs of any single sender or any subset of $m-1$ senders.

2. Lower Bounds without Preshared Entanglement:
   In contrast, the authors prove that without preshared entanglement, any protocol achieving a high success probability requires $\Omega(\sqrt{n})$ communication from at least one sender.

   • This lower bound holds even when the senders are allowed to send unrestricted quantum messages (qubits) to Bob, provided they do not share entanglement beforehand.
   • The proof leverages known lower bounds for the bipartite Hidden Matching problem and extends them to the multipartite setting.

3. The Separation:
   The combination of the upper bound ($O(\log n)$) with entanglement and the lower bound ($\Omega(\sqrt{n})$) without entanglement establishes an exponential separation. This proves that classical communication assisted by multipartite entanglement is exponentially more powerful than unrestricted quantum communication without preshared entanglement.

4. Cryptographic Application: Bounded-Storage Cryptography:
   The communication protocol is applied to construct a seeded two-source randomness extractor ($Ext_2$) for weak random sources.

   • Unentangled Side-Information: To compromise the extractor (i.e., distinguish the output from uniform), an adversary with unentangled quantum side-information requires polynomial-size quantum memory ($O(\sqrt{n})$).
   • Entangled Side-Information: If the adversary possesses a small amount of preshared entanglement (specifically, two entangled states of $O(\log n)$ qubits, one for each source), they can compromise the extractor.
   • Result: This establishes an exponential separation between the power of entangled and unentangled quantum side-information in the context of bounded-storage cryptography.

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

• Communication Complexity: It provides the first demonstration of an exponential separation in a multipartite setting where classical communication with entanglement outperforms quantum communication without entanglement. This identifies multipartite entanglement not merely as a substitute for quantum communication, but as a resource that can strictly enhance it.
• Cryptography: The work reveals a qualitative distinction in security against quantum adversaries. It shows that security guarantees against adversaries with unentangled quantum memory do not necessarily hold against 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 this fundamental separation. They note that while their construction is not optimized for extraction parameters, it successfully highlights the vulnerability of certain extractors to entangled side-information.

The paper concludes by suggesting that multipartite entanglement should be viewed as a computational resource extending beyond the generation of nonlocal correlations, opening directions for future research in interactive models, noisy settings, and other cryptographic primitives like privacy amplification.