Non-locality and Communication Complexity

Abstract

Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, entanglement, and interference. In this review we study the information counterpart of computing. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. We review the area of quantum communication complexity, and show how it connects the foundational physics questions regarding non-locality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on non-locality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics, and could even yield new proposals for experiments that test the foundations of physics.

Survey paper, 63 pages LaTeX. A reformatted version will appear in Reviews of Modern Physics

References in corpus (23)

• Device-independent security of quantum cryptography against collective attacks
• Hidden Variables and the Two Theorems of John Bell
• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Bounding the set of quantum correlations
• Bell inequality violation with two remote atomic qubits
• The Communication Cost of Simulating Bell Correlations
• Testing the Hilbert space dimension
• Grothendieck's constant and local models for noisy entangled quantum states
• A lower bound on the dimension of a quantum system given measured data
• Unbounded violation of tripartite Bell inequalities
• Non-locality distillation and post-quantum theories with trivial communication complexity
• Detection loophole in asymmetric Bell experiments
• Distilling Non-Locality
• Implausible Consequences of Superstrong Nonlocality
• Tsirelson's Problem
• Combinatorics and Quantum Nonlocality
• Simulation of partial entanglement with nonsignaling resources
• Simulation of bipartite qudit correlations
• A generalized Grothendieck inequality and entanglement in XOR games
• Simultaneous Communication Protocols with Quantum and Classical Messages
• Simulating Quantum Correlations with Finite Communication
• Experimental quantum "Guess my Number" protocol using multiphoton entanglement
• A simple demonstration of Bell's theorem involving two observers and no probabilities or inequalities

Cited by in corpus (337)

• Bell nonlocality
• Quantum Resource Theories
• Quantum algorithms: an overview
• The European Quantum Technologies Roadmap
• Photonic quantum information processing: a concise review
• Contextuality supplies the magic for quantum computation
• Quantum discord as resource for remote state preparation
• Local orthogonality as a multipartite principle for quantum correlations
• Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
• Nanofabricated and integrated colour centres in silicon carbide with high-coherence spin-optical properties
• The SWAP test and the Hong-Ou-Mandel effect are equivalent
• Detecting genuine multipartite quantum non-locality -- a simple approach and generalization to arbitrary dimension
• All noncontextuality inequalities for the n-cycle scenario
• Nonlocal correlations in the star-network configuration
• Large violation of Bell inequalities with low entanglement
• Genuine hidden quantum nonlocality
• Super-activation of quantum non-locality
• Nonlinear Bell inequalities tailored for quantum networks
• Polynomial Bell inequalities
• Experimental Verification of Multipartite Entanglement in Quantum Networks
• Bell nonlocality and Bayesian game theory
• Quantum networks reveal quantum nonlocality
• Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
• Quantum Random Access Codes using Single $d$-level Systems
• Quantum superposition of the order of parties as a communication resource
• Contextual advantage for state discrimination
• Entanglement in indistinguishable particle systems
• Bounding the set of finite dimensional quantum correlations
• Entropic Inequalities and Marginal Problems
• Computationally Efficient Nonlinear Bell Inequalities for General Quantum Networks
• Genuine tripartite nonlocality and entanglement in curved spacetime
• Cavity-enhanced quantum network nodes
• Quantum nonlocality does not imply entanglement distillability
• Enhancing Generative Models via Quantum Correlations
• Semi-device-independent bounds on entanglement
• Experimental non-locality in a quantum network
• Guaranteed violation of a Bell inequality without aligned reference frames or calibrated devices
• Experimental Quantum Fingerprinting
• A scattering quantum circuit for measuring Bell's time inequality: a nuclear magnetic resonance demonstration using maximally mixed states
• Memory cost of quantum contextuality
• Experimental distribution of entanglement with separable carriers
• Machine learning non-local correlations
• State independent contextuality advances one-way communication
• Cloning and Broadcasting in Generic Probabilistic Theories
• Semidefinite tests for quantum network topologies
• Genuine multipartite nonlocality is intrinsic to quantum networks
• Quantum Fingerprinting with Coherent States and a Constant Mean Number of Photons
• Causal hierarchy of multipartite Bell nonlocality
• Experimental fully contextual correlations
• Enabling computation of correlation bounds for finite-dimensional quantum systems via symmetrisation
• Nonlocality of Symmetric States
• Classical simulation of entanglement swapping with bounded communication
• Semidefinite programming relaxations for quantum correlations
• Facets of bipartite nonlocality sharing by multiple observers via sequential measurements
• Bounding the sets of classical and quantum correlations in networks
• Single-copy entanglement detection
• Entanglement of a bipartite channel
• Quantum communication complexity advantage implies violation of a Bell inequality
• Quantifying Bell non-locality with the trace distance
• Bell-type Inequalities for Arbitrary Non-Cyclic Networks
• Unbounded violations of bipartite Bell Inequalities via Operator Space theory
• Two-way communication with a single quantum particle
• Observation of quantum fingerprinting beating the classical limit
• Conference key agreement in a quantum network
• Quantum contextuality provides communication complexity advantage
• Preparation contextuality as an essential feature underlying quantum communication advantage
• Basic exclusivity graphs in quantum correlations
• Entanglement and thermodynamics in general probabilistic theories
• Quantum Communication with Coherent States and Linear Optics
• Non-adaptive Measurement-based Quantum Computation and Multi-party Bell Inequalities
• Experimental Quantum Network Coding
• A framework for the study of symmetric full-correlation Bell-like inequalities
• Bound non-locality and activation
• Experimental Bell inequality violation without the postselection loophole
• Test of Genuine Multipartite Nonlocality Without Inequality
• Sharing of tripartite nonlocality by multiple observers measuring sequentially at one side
• Quantum teleportation with identical particles
• Characterizing finite-dimensional quantum behavior
• Experimental quantum advantage with quantum coupon collector
• Exploring the Local Orthogonality Principle
• Entropic inequalities as a necessary and sufficient condition to noncontextuality and locality
• High-dimensional quantum communication complexity beyond strategies based on Bell's theorem
• If no information gain implies no disturbance, then any discrete physical theory is classical
• Experimental Aspects of Indefinite Causal Order in Quantum Mechanics
• Bell inequalities with no quantum violation and unextendible product bases
• Entanglement Structure: Entanglement Partitioning in Multipartite Systems and Its Experimental Detection Using Optimizable Witnesses
• NetQASM -- A low-level instruction set architecture for hybrid quantum-classical programs in a quantum internet
• Surface Code Error Correction on a Defective Lattice
• The local content of all pure two-qubit states
• Concentration phenomena in the geometry of Bell correlations
• Experimental two-way communication with one photon
• Nonlocality free wirings and the distinguishability between Bell boxes
• Elemental and tight monogamy relations in nonsignalling theories
• Tight Bell inequalities with no quantum violation from qubit unextendible product bases
• Device-independent lower bounds on the conditional von Neumann entropy
• Testing dimension and non-classicality in communication networks
• Multipartite quantum nonlocality under local decoherence
• Quantum Computing: Lecture Notes
• Bounding quantum correlations with indefinite causal order
• Pearson Correlation Coefficient as a measure for Certifying and Quantifying High Dimensional Entanglement
• Violations of locality and free choice are equivalent resources in Bell experiments
• Translationally invariant multipartite Bell inequalities involving only two-body correlators
• One-Shot Manipulation of Dynamical Quantum Resources
• Analysing quantum systems with randomised measurements
• Informationally restricted quantum correlations
• Quantum Bilinear Optimization
• Experimental certification of contextuality, coherence and dimension in a programmable universal photonic processor
• Communication tasks with infinite quantum-classical separation
• Bounding quantum contextuality with lack of third-order intereference
• Experimental Test of the Quantum Violation of the Noncontextuality Inequalities for the n-Cycle Scenario
• Loophole-free Bell test based on local precertification of photon's presence
• Bell scenarios with communication
• Hardy's nonlocality argument as witness for post-quantum correlation
• Certifying entangled measurements in known Hilbert spaces
• On the state complexity of semi-quantum finite automata
• Feasibility of loophole-free nonlocality tests with a single photon
• Client-Server Identification Protocols with Quantum PUF
• Resource-efficient high-dimensional entanglement detection via symmetric projections
• Quantum Correlations and Quantum Non-locality: a review and a few new ideas
• Leggett-Garg Macrorealism and temporal correlations
• Narratives of Quantum Theory in the Age of Quantum Technologies
• Epistemic view of quantum states and communication complexity of quantum channels
• Converting quantum coherence to genuine multipartite entanglement and nonlocality
• Nonlocality of All Quantum Networks
• Bell tests for continuous variable systems using hybrid measurements and heralded amplifiers
• Quantum and classical bounds for two-state overlaps
• Correlations of entangled quantum states cannot be classically simulated
• Oblivious communication game, self-testing of projective and non-projective measurements and certification of randomness
• Design and Experimental Performance of Local Entanglement Witness Operators
• Generalized Bell Inequality Experiments and Computation
• Entanglement in prepare-and-measure scenarios: many questions, a few answers
• Measurement incompatibility and quantum advantage in communication
• Survey on the Bell nonlocality of a pair of entangled qudits
• Maximum nonlocality and minimum uncertainty using magic states
• Semi-device-independent certification of entanglement in superdense coding
• Entanglement in dissipative dynamics of identical particles
• Device independent certification of a quantum delayed choice experiment
• A histories perspective on characterising quantum non-locality
• Convex separation from convex optimization for large-scale problems
• Bayes' rule, generalized discord, and nonextensive thermodynamics
• Robust multipartite quantum correlations without complex encodings
• Local quasi hidden variable modelling and violations of Bell-type inequalities by a multipartite quantum state
• Information and communication in polygon theories
• Information-theoretic constraints on correlations with indefinite causal order
• Quantum communication complexity beyond Bell nonlocality
• Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?
• Quantum entanglement in cosmology
• Tight upper bound for the maximal quantum value of the Svetlichny operators
• Entanglement as upper bounded for the nonlocality of a general two-qubit system
• Nonlocality and Entanglement for Symmetric States
• Classical Cost of Transmitting a Qubit
• Generalizations of the distributed Deutsch-Jozsa promise problem
• Bell inequalities from variable elimination methods
• Memory cost for simulating all quantum correlations of the Peres-Mermin scenario
• Variational Quantum Optimization of Nonlocality in Noisy Quantum Networks
• Genuine four-partite Bell nonlocality in the curved spacetime
• Performances and robustness of quantum teleportation with identical particles
• Macroscopic non-contextuality as a principle for Almost Quantum Correlations
• Bounding and simulating contextual correlations in quantum theory
• Graph-theoretic strengths of contextuality
• Quantum violation of local causality in urban network with hybrid photonic technologies
• Detecting nonlocality of noisy multipartite states with the CHSH inequality
• Mutually Unbiased Balanced Functions & Generalized Random Access Codes
• Shared randomness and device-independent dimension witnessing
• Higher dimensional communication complexity problems: classical protocols vs quantum ones based on Bell's Theorem or prepare-transmit-measure schemes
• Simple Communication Complexity Separation from Quantum State Antidistinguishability
• Entanglement Verification with Deep Semi-supervised Machine Learning
• What Can Quantum Information Theory Offer to Quantum Chemistry?
• Increased Certification of Semi-device Independent Random Numbers using Many Inputs and More Postprocessing
• Generalized XOR games with $d$ outcomes and the task of non-local computation
• Bell Experiments with Random Destination Sources
• Nonlocality with ultracold atoms in a lattice
• Nonlocality of three-qubit Greenberger-Horne-Zeilinger-symmetric states
• Complexity of causal order structure in distributed quantum information processing and its trade-off with entanglement
• Quantum cryptography beyond key distribution: theory and experiment
• Closing the detection loophole in multipartite Bell tests using GHZ states
• Probing the Non-Classicality of Temporal Correlations
• Device-independent self-testing of unsharp measurements
• Optimized detection of high-dimensional entanglement
• Weak quantum discord
• Communication cost of classically simulating a quantum channel with subsequent rank-1 projective measurement
• Genuine multipartite nonlocality with causal-diagram postselection
• Information-based measure of nonlocality
• Device-independent randomness based on a tight upper bound of the maximal quantum value of chained inequality
• Distilling Nonlocality in Quantum Correlations
• Genuine multipartite nonlocality in the one-dimensional ferromagnetic spin-1/2 chain
• Interoperability in encoded quantum repeater networks
• Quantum bounds on multiplayer linear games and device-independent witness of genuine tripartite entanglement
• Quantum advantages of communication complexity from Bell nonlocality
• Simple conditions constraining the set of quantum correlations
• High-dimensional entanglement witnessed by correlations in arbitrary bases
• Self-testing and certification using trusted quantum inputs
• Hierarchy of multipartite nonlocality in the nonsignaling scenario
• Regarding the Maximal Qubit Violations of n-Locality in Star and Chain Networks
• A unified view on Hardy's paradox and the CHSH inequality
• Trade-offs in multi-party Bell inequality violations in qubit networks
• Quantum Metrology in Correlated Environments
• The Mathematics of Entanglement
• Sharing preparation contextuality in Bell experiment by arbitrary pair of sequential observers
• Communication-efficient Quantum Algorithm for Distributed Machine Learning
• Adaptive advantage in entanglement-assisted communications
• Tsirelson's bound and supersymmetric entangled states
• Quantum stochastic communication via high-dimensional entanglement
• Advantage of Quantum Theory Over Non-classical Models of Communication
• Device independent witness of arbitrary dimensional quantum systems employing binary outcome measurements
• Noise-induced distributed entanglement in atom-cavity-fiber system
• High fidelity GHZ generation within nearby nodes
• Bounding the persistency of the nonlocality of W states
• The Information Content of Systems in General Physical Theories
• Necessary and sufficient optimality conditions for classical simulations of quantum communication processes
• Certification of qubits in the prepare-and-measure scenario with large input alphabet and connections with the Grothendieck constant
• Communication Complexity of Channels in General Probabilistic Theories
• Quantum Advantages in (n,d)->1 Random Access Codes
• Certifying the Classical Simulation Cost of a Quantum Channel
• Optimal and tight Bell inequalities for state-independent contextuality sets
• Numerically assisted determination of local models in network scenarios
• Entanglement Structure Detection via Computer Vision
• Revealing Hidden Genuine Tripartite Nonlocality
• Bell's Inequalities, Superquantum Correlations, and String Theory
• A quantum information approach to statistical mechanics
• A general bound for the dimension of quantum behaviours in the prepare-and-measure scenario
• Quantum states cannot be transmitted efficiently classically
• Classical analogue of quantum superdense coding and communication advantage of a single quantum system
• Bounding quantum theory with the exclusivity principle in a two-city experiment
• Three-players conflicting interest games and nonlocality
• Generalizing optimal Bell inequalities
• Experimental verification of time-order-dependent correlations in three-qubit Greenberger-Horne-Zeilinger-class states
• Visibility-based hypothesis testing using higher-order optical interference
• Schmidt number criterion via general symmetric informationally complete measurements
• Unbounded quantum advantage in communication complexity measured by distinguishability
• Experimentally friendly approach towards nonlocal correlations in multisetting N -partite Bell scenarios
• Approximate simulation of entanglement with a linear cost of communication
• On the tightness of correlation inequalities with no quantum violation
• Undecidability in Physics: a Review
• Towards Holographic Quantum Energy Teleportation
• Local simulation of singlet statistics for restricted set of measurement
• Extending the Known Region of Nonlocal Boxes that Collapse Communication Complexity
• All tight correlation Bell inequalities have quantum violations
• Cryptographic Quantum Bound on Nonlocality
• Sampling quantum nonlocal correlations with high probability
• Random quantum correlations are generically non-classical
• Quantum sketching protocols for Hamming distance and beyond
• Single-photon pump by Cooper-pair splitting
• Bell inequalities for nonlocality depth
• Exponential Lower Bounds for Polytopes in Combinatorial Optimization
• Random constructions in Bell inequalities: A survey
• Unmasking the Polygamous Nature of Quantum Nonlocality
• Quantifying multiparticle entanglement with randomized measurements
• Bound entangled states are useful in prepare-and-measure scenarios
• Locality and entanglement of indistinguishable particles
• Immunity of information encoded in decoherence-free subspaces to particle loss
• Spin-parity effect in violation of bell's inequalities for entangled states of parallel polarization
• Entanglement and measurement-induced nonlocality of mixed maximally entangled states in multipartite dynamics
• Werner gap in presence of simple coloured noise
• Tight upper bound on the quantum value of Svetlichny operators under local filtering and hidden genuine nonlocality
• Optimal measurements for nonlocal correlations
• Bell non-locality using tensor networks and sparse recovery
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement
• Tsirelson bounds for quantum correlations with indefinite causal order
• Trade-off relation among genuine three-qubit nonlocalities in four-qubit systems
• The Complexity of Being Entangled
• Note on Product-Form Monogamy Relations for Nonlocality and Other Correlation Measures
• All two-party facet Bell inequalities are violated by Almost Quantum correlations
• Experimental construction of a symmetric three-qubit entangled state and its utility in testing the violation of a Bell inequality on an NMR quantum simulator
• $(n,m,p)$-type quantum network configuration and its nonlocality
• Simple and tight monogamy relations for a class of Bell inequalities
• Semi-device-independent certification of quantum non-Markovianity using sequential Random Access Codes
• An Effective Way of Characterizing the Quantum Nonlocality
• One-shot manipulation of coherence in dynamic quantum resource theory
• Communication complexity of promise problems and their applications to finite automata
• Quantum eigenstate broadcasting assisted by a coherent link
• Maximum violation of Wigner inequality for two-spin entangled states with parallel and antiparallel polarizations
• Nonlocal Josephson diode effect in minimal Kitaev chains
• Simple algorithm for computing the communication complexity of quantum communication processes
• Paradoxical consequences of multipath coherence: perfect interaction-free measurements
• Classical description of quantum randomness using stochastic gauge systems
• One-time Pad Encryption Model for Non-local Correlations
• Compression of Entanglement Improves Quantum Communication
• Topics in Quantum Networking
• Bell tests with random measurements require very high detection efficiencies
• Tight upper bound for the maximal expectation value of the $N$-partite generalized Svetlichny operator
• Undetectable Werner states using linear Bell inequalities
• A No-go theorem for device-independent security in relativistic causal theories
• Proceedings of the 7th International Workshop on Physics and Computation
• Minimum Detection Efficiencies for Loophole-free Genuine Nonlocality Tests
• CP symmetry and thermal effects on Dirac bi-spinor spin-parity local correlations
• How to avoid (apparent) signaling in Bell tests
• Uncertainty principle as post-quantum nonlocality witness for continuous variable multi-mode scenario
• Stronger Nonlocality in GHZ States: A Step Beyond the Conventional GHZ Paradox
• Bound on Bell Inequalities by Fraction of Determinism and Reverse Triangle Inequality
• Extended Bell inequality and maximum violation
• The role of entanglement in energy-restricted communication and randomness generation
• Maximum tri-partite Hardy's nonlocality respecting all bi-partite principles
• Quantum resources of the steady-state of three coupled qubits: Microscopic versus Phenomenological model
• Superlinear advantage for exact quantum algorithms
• Reality, Causality, and Quantum Theory
• Examining the effect of quantum strategies on symmetric conflicting interest games
• Precisely resolve energy-time entanglement by dual channel Fabry-Perot interferometry
• Quantum Strategic Game Theory
• General theory of quantum fingerprinting network
• Generalized Iterative Formula for Bell Inequalities
• Some remarks on Bell non-locality and Einstein-Podolsky-Rosen steering of bipartite states
• General spin systems without genuinely multipartite nonlocality
• Quantum advantage for distributed computing without communication
• Deterministic all-versus-nothing proofs of Bell nonlocality based on non-stabilizer states
• Multi-party quantum fingerprinting with weak coherent pulses: circuit design and protocol analysis
• On fully entangled fraction and quantum conditional entropies for states with maximally mixed marginals
• Quantum strategies for simple 2-player XOR games
• Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem
• Time-space tradeoffs for two-way finite automata
• Seedless extractors for device-independent quantum cryptography
• Single trusted qubit is necessary and sufficient for quantum realisation of extremal no-signaling correlations
• The communication complexity of XOR games via summing operators
• Remarks on the tensor product structure of no-signaling theories
• (Almost-)Quantum Bell Inequalities and Device-Independent Applications
• Nonlocal and quantum advantages in network coding for multiple access channels
• Quantum correlation generation capability of experimental processes
• SOS decomposition for general Bell inequalities in two qubits systems and its application to quantum randomness
• Computational Perspectives on Bell Inequalities and Many-body Quantum Correlations
• Hybrid no-signaling-quantum correlations
• Enhancing entanglement and total correlations dynamics via local unitaries
• Phase-sensitive superposition of quantum states
• High-performance parallel classical scheme for simulating shallow quantum circuits
• Parity Cross-Resonance: A Multiqubit Gate
• Quantum Advantage in Identifying the Parity of Permutations with Certainty
• Better Protocol for XOR Game using Communication Protocol and Nonlocal Boxes
• Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography
• Inter-qubit correlation dynamics driven by mutual interactions
• Nonlocality in Continuous-Variable Quantum Networks
• Any Two Qubit State Has Non Zero Quantum Discord Under Global Unitary Operations
• Advantage in two-way communication using non-classical states of light
• Gottesman-Knill Limit on One-way Communication Complexity: Tracing the Quantum Advantage down to Magic Resources
• Suboptimality of Parity for Distilling Correlations with Nontrivial Marginals
• The structure of optimal and nearly-optimal quantum strategies for non-local XOR games
• Quantum game players can have advantage without discord
• Generalized XOR non-locality games with graph description on a square lattice
• Oracle problems as communication tasks and optimization of quantum algorithms