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

• URL: http://arxiv.org/abs/2607.27957v1
• Date: Thu, 30 Jul 2026 10:04:53 GMT
• Title: Exponential Advantage of Multipartite Entanglement over Quantum Communication with Applications to Bounded-Storage Cryptography
• Abstract summary: We show that a shared Greenberger-Horne-Zeilinger state enables completion of a task using only logarithmically many bits of classical communication from each sender.<n>Without preshared entanglement, any protocol achieving high success probability requires communication from at least one sender.<n>As a cryptographic application, we construct a seeded two-source extractor and establish an exponential separation between entangled and unentangled quantum side-information.
• Score: 0.5862480696321741
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish an exponential communication advantage enabled by multipartite quantum entanglement. Building on the bipartite Hidden Matching problem, we introduce a communication task involving multiple spatially separated senders and a single receiver. We show that a shared Greenberger-Horne-Zeilinger state enables completion of this task using only logarithmically many bits of classical communication from each sender. In contrast, without preshared entanglement, any protocol achieving high success probability requires polynomial communication from at least one sender, even when \emph{quantum} communication is allowed. Thus, classical communication assisted by multipartite entanglement can be exponentially more powerful than quantum communication without preshared entanglement. As a cryptographic application, we construct a seeded two-source randomness extractor and establish an exponential separation between entangled and unentangled quantum side-information. Specifically, compromising the extractor with two unentangled quantum states storing information about the two sources, respectively, requires polynomial-size memory, whereas exponentially smaller quantum memory suffices in the presence of a small amount of shared entanglement.

Related papers

• Communication Advantages from Quantum Dense Network Coding [1.7188280334580195]
  We introduce quantum dense network coding -- a protocol that transmits the output of a non-Boolean function to a receiver using provably half as many qubits as bits for each sender.<n>We show this advantage requires both shared entanglement and quantum communication, is robust to noise, and the gap in success probability between quantum and classical communication can be amplified exponentially.<n>We show that dense network coding gives rise to a novel, information-theoretically secure, quantum cryptographic protocol, which we call measurement-device-independent quantum key growing.
  arXiv  Detail & Related papers  (2026-07-09T06:08:43Z)
• Extendibility limits quantum-secured communication and key distillation [4.079147243688764]
  We study the task of secret-key distillation from bipartite states and point-to-point quantum channels. We extend our formalism to private communication over a quantum channel assisted by forward classical communication.
  arXiv  Detail & Related papers  (2024-10-28T18:00:11Z)
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement [0.0]
  Quantum resources offer advantages over classical methods in addressing this challenge. We show that when the receiver and the senders share a multi-qubit Greenberger-Horne-Zeilinger (GHZ) state, certain global functions of the distributed inputs can be computed with only one bit of classical communication from each sender. We also show that the entanglement-based protocol exhibits significant robustness under white noise.
  arXiv  Detail & Related papers  (2024-09-20T05:17:09Z)
• Realizing fracton order from long-range quantum entanglement in programmable Rydberg atom arrays [45.19832622389592]
  Storing quantum information requires battling quantum decoherence, which results in a loss of information over time. To achieve error-resistant quantum memory, one would like to store the information in a quantum superposition of degenerate states engineered in such a way that local sources of noise cannot change one state into another. We show that this platform also allows to detect and correct certain types of errors en route to the goal of true error-resistant quantum memory.
  arXiv  Detail & Related papers  (2024-07-08T12:46:08Z)
• Information Carried by a Single Particle in Quantum Multiple-Access Channels [13.821363169821046]
  Non-classical features of quantum systems have the potential to strengthen the way we currently exchange information. We compare how well multi-party information can be transmitted to a single receiver using just one classical or quantum particle.
  arXiv  Detail & Related papers  (2023-01-06T14:01:56Z)
• Oblivious Quantum Computation and Delegated Multiparty Quantum Computation [61.12008553173672]
  We propose a new concept, oblivious computation quantum computation, where secrecy of the input qubits and the program to identify the quantum gates are required. Exploiting quantum teleportation, we propose a two-server protocol for this task. Also, we discuss delegated multiparty quantum computation, in which, several users ask multiparty quantum computation to server(s) only using classical communications.
  arXiv  Detail & Related papers  (2022-11-02T09:01:33Z)
• Conference key agreement in a quantum network [67.410870290301]
  Quantum conference key agreement (QCKA) allows multiple users to establish a secure key from a shared multi-partite entangled state. In a quantum network, this protocol can be efficiently implemented using a single copy of a N-qubit Greenberger-Horne-Zeilinger (GHZ) state to distil a secure N-user conference key bit.
  arXiv  Detail & Related papers  (2022-07-04T18:00:07Z)
• Entanglement-assisted quantum communication with simple measurements [0.0]
  Dense coding is the seminal example of how entanglement can boost qubit communication. We show that measurements enable strong and sometimes even optimal entanglement-assisted qubit communication protocols. Our results reveal that there are scenarios in which the power of entanglement in enhancing quantum communication can be harvested in simple and scalable optical experiments.
  arXiv  Detail & Related papers  (2022-05-19T14:47:38Z)
• Quantum Semantic Communications for Resource-Efficient Quantum Networking [52.3355619190963]
  This letter proposes a novel quantum semantic communications (QSC) framework exploiting advancements in quantum machine learning and quantum semantic representations. The proposed framework achieves approximately 50-75% reduction in quantum communication resources needed, while achieving a higher quantum semantic fidelity.
  arXiv  Detail & Related papers  (2022-05-05T03:49:19Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)
• Computation-aided classical-quantum multiple access to boost network communication speeds [61.12008553173672]
  We quantify achievable quantum communication rates of codes with computation property for a two-sender cq-MAC. We show that it achieves the maximum possible communication rate (the single-user capacity), which cannot be achieved with conventional design.
  arXiv  Detail & Related papers  (2021-05-30T11:19:47Z)
• Experimental quantum conference key agreement [55.41644538483948]
  Quantum networks will provide multi-node entanglement over long distances to enable secure communication on a global scale. Here we demonstrate quantum conference key agreement, a quantum communication protocol that exploits multi-partite entanglement. We distribute four-photon Greenberger-Horne-Zeilinger (GHZ) states generated by high-brightness, telecom photon-pair sources across up to 50 km of fibre.
  arXiv  Detail & Related papers  (2020-02-04T19:00:31Z)

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.