Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement
arXiv:2409.13223 · doi:10.1103/PhysRevA.111.032617
Abstract
Distributed computing, involving multiple servers collaborating on designated computations, faces a critical challenge in optimizing inter-server communication -- an issue central to the study of communication complexity. Quantum resources offer advantages over classical methods in addressing this challenge. In this work, we investigate a distributed computing scenario with multiple senders and a single receiver, establishing a scalable advantage of multipartite quantum entanglement in mitigating communication complexity. Specifically, we demonstrate that when the receiver and the senders share a multi-qubit Greenberger-Horne-Zeilinger (GHZ) state -- a quintessential form of genuine multipartite entanglement -- certain global functions of the distributed inputs can be computed with only one bit of classical communication from each sender. In contrast, without entanglement, two bits of communication are required from all but one sender. Consequently, quantum entanglement reduces communication overhead by (n-1) bits for n senders, allowing for arbitrary scaling with an increasing number of senders. We also show that the entanglement-based protocol exhibits significant robustness under white noise, thereby establishing the potential for experimental realization of this novel quantum advantage.
6 pages, 2 figures; Comments are welcome
References in corpus (44)
- Quantum entanglement
- Three qubits can be entangled in two inequivalent ways
- Bell nonlocality
- Entanglement detection
- Quantum fingerprinting
- Hidden Variables and the Two Theorems of John Bell
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Four qubits can be entangled in nine different ways
- Generation and manipulation of Schrödinger cat states in Rydberg atom arrays
- Non-locality and Communication Complexity
- Entanglement-Assisted Classical Capacity of Noisy Quantum Channels
- Substituting Quantum Entanglement for Communication
- 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
- A limit on nonlocality in any world in which communication complexity is not trivial
- A compact ion-trap quantum computing demonstrator
- Observation of multi-component atomic Schrödinger cat states of up to 20 qubits
- Self-testing of quantum systems: a review
- Experimental demonstration of a hyper-entangled ten-qubit Schrödinger cat state
- Separability criteria for genuine multiparticle entanglement
- Classification of multi-qubit mixed states: separability and distillability properties
- Violation of Bell's inequality: criterion for quantum communication complexity advantage
- Multi-Particle Entanglement Purification Protocols
- On the von Neumann capacity of noisy quantum channels
- No quantum advantage for nonlocal computation
- Quantum Entanglement and Communication Complexity
- Multiparticle entanglement purification for two-colorable graph states
- Multiparty Quantum Communication Complexity
- Benchmarking one-shot distillation in general quantum resource theories
- Purification of genuine multipartite entanglement
- Distillation of multipartite entanglement by complementary stabilizer measurements
- No-hypersignaling principle
- Classical information storage in an -level quantum system
- Explicit product ensembles for separable quantum states
- Creating and controlling global Greenberger-Horne-Zeilinger entanglement on quantum processors
- Thermodynamic Signatures of Genuinely Multipartite Entanglement
- Multipartite entanglement outperforming bipartite entanglement under limited quantum system sizes
- Quantum communication complexity beyond Bell nonlocality
- Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?
- Distilling Nonlocality in Quantum Correlations
- Parallel Self-Testing of the GHZ State with a Proof by Diagrams
- Entanglement Purification with Quantum LDPC Codes and Iterative Decoding
- Quantum Nonlocality: Multi-copy Resource Inter-convertibility & Their Asymptotic Inequivalence
- Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity
- One-time Pad Encryption Model for Non-local Correlations
Cited by in corpus (4)
- Detecting genuine multipartite entanglement using moments of positive maps
- Stronger Nonlocality in GHZ States: A Step Beyond the Conventional GHZ Paradox
- Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
- Oracle problems as communication tasks and optimization of quantum algorithms