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

This paper investigates whether multipartite entanglement—a complex form of quantum correlation that cannot be reduced to bipartite interactions—can provide an exponential advantage in communication complexity. While bipartite entanglement is known to offer such advantages, the potential of multipartite states in distributed tasks remained largely unexplored.

The authors introduce a multipartite version of the Hidden Matching problem, where multiple spatially separated senders (Alices) must communicate with a single receiver (Bob) to solve a global relation. They compare the communication costs under different models: classical communication with and without shared entanglement, and quantum communication without preshared entanglement. They also construct a two-source randomness extractor to demonstrate how this communication advantage translates into a cryptographic separation between entangled and unentangled quantum side-information.

The study proves that sharing a Greenberger-Horne-Zeilinger (GHZ) state allows the senders to complete the multipartite Hidden Matching task using only logarithmic bits of classical communication. Conversely, without preshared entanglement, any protocol that achieves high success probability requires polynomial communication from at least one sender, even if that sender is allowed to use quantum communication. This establishes an exponential gap between entanglement-assisted classical communication and unassisted quantum communication. Furthermore, the authors show that this gap applies to bounded-storage cryptography: an adversary with entangled quantum memory can compromise a randomness extractor using exponentially less storage than an adversary restricted to unentangled quantum memory.