No quantum advantage for nonlocal computation

Abstract

We investigate the problem of "nonlocal" computation, in which separated parties must compute a function with nonlocally encoded inputs and output, such that each party individually learns nothing, yet together they compute the correct function output. We show that the best that can be done classically is a trivial linear approximation. Surprisingly, we also show that quantum entanglement provides no advantage over the classical case. On the other hand, generalized (i.e. super-quantum) nonlocal correlations allow perfect nonlocal computation. This gives new insights into the nature of quantum nonlocality and its relationship to generalised nonlocal correlations.

4 pages

Cited by in corpus (121)

• Bell nonlocality
• Information Causality as a Physical Principle
• Specker's Parable of the Over-protective Seer: A Road to Contextuality, Nonlocality and Complementarity (PLUS AN ERRATUM)
• Almost quantum correlations
• Guess your neighbour's input: a multipartite non-local game with no quantum advantage
• Quasi-quantization: classical statistical theories with an epistemic restriction
• Introduction to the book "Quantum Theory: Informational Foundations and Foils"
• Quantum from principles
• The completeness of quantum theory for predicting measurement outcomes
• Maximal violation of the I3322 inequality using infinite dimensional quantum systems
• Non-locality distillation and post-quantum theories with trivial communication complexity
• Recovering part of the quantum boundary from information causality
• Observation of tunable Popescu-Rohrlich correlations through post-selection of a gaussian state
• Limits on non-local correlations from the structure of the local state space
• Distilling Non-Locality
• Entanglement: Quantum or Classical?
• Closed sets of non-local correlations
• Emergence of Quantum Correlations from Non-Locality Swapping
• A purification postulate for quantum mechanics with indefinite causal order
• Macroscopically local correlations can violate information causality
• Machine Learning meets Quantum Foundations: A Brief Survey
• Semidefinite programming relaxations for quantum correlations
• Photonic source of heralded GHZ states
• Entanglement and thermodynamics in general probabilistic theories
• Information causality from an entropic and a probabilistic perspective
• Bound non-locality and activation
• Bell inequalities with no quantum violation and unextendible product bases
• How device-independent approaches change the meaning of physical theory
• A channel-based framework for steering, non-locality and beyond
• Tight Bell inequalities with no quantum violation from qubit unextendible product bases
• Simulating all non-signalling correlations via classical or quantum theory with negative probabilities
• Dimension of physical systems, information processing, and thermodynamics
• Closed sets of correlations: answers from the zoo
• Monotone Measures for Non-Local Correlations
• Bridging the gap between general probabilistic theories and the device-independent framework for nonlocality and contextuality
• Relativistic independence bounds nonlocality
• Nonlocality Without Entanglement: Quantum Theory and Beyond
• Quantum correlations from simple assumptions
• Bounding quantum contextuality with lack of third-order intereference
• Bounds for Non-Locality Distillation Protocols
• Almost quantum correlations violate the no-restriction hypothesis
• Quantum Correlations and Quantum Non-locality: a review and a few new ideas
• Narratives of Quantum Theory in the Age of Quantum Technologies
• Self-testing of physical theories, or, is quantum theory optimal with respect to some information-processing task?
• Semi-definite programming and quantum information
• Geometry of the quantum set on no-signaling faces
• A histories perspective on characterising quantum non-locality
• Network nonlocality sharing via weak measurements in the extended bilocal scenario
• Postquantum common-cause channels: the resource theory of local operations and shared entanglement
• Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems
• Information-theoretic constraints on correlations with indefinite causal order
• General Bayesian theories and the emergence of the exclusivity principle
• A formalism for steering with local quantum measurements
• Bipartite Units of Non-Locality
• Universal gaps for XOR games from estimates on tensor norm ratios
• Non-classical correlations in quantum mechanics and beyond
• Spin operator, Bell nonlocality and Tsirelson bound in quantum-gravity induced minimal-length quantum mechanics
• Generalized XOR games with $d$ outcomes and the task of non-local computation
• Concavity of the quantum body for any given dimension
• Bounding the plausibility of physical theories in a device-independent setting via hypothesis testing
• Couplers for Non-Locality Swapping
• Quantum bounds on multiplayer linear games and device-independent witness of genuine tripartite entanglement
• Quantum Information Processing with Adversarial Devices
• Simple conditions constraining the set of quantum correlations
• Characterising the Performance of XOR Games and the Shannon Capacity of Graphs
• The principle of information symmetry constrains the state-space in any physical theory
• Approaching the Tsirelson bound with a Sagnac source of polarization-entangled photons
• Towards correlation self-testing of quantum theory in the adaptive Clauser-Horne-Shimony-Holt game
• Naturally restricted subsets of nonsignaling correlations: typicality and convergence
• Certificates of quantum many-body properties assisted by machine learning
• Multiplicative Bell Inequalities
• Experimental Test of Nonlocality Limits from Relativistic Independence
• Nonlinear Schrödinger equations and generalized Heisenberg uncertainty principle violating the principle of estimation independence
• Information Causality in the Quantum and Post-Quantum Regime
• Many-box locality
• Local randomness in Hardy's correlations: Implications from information causality principle
• Generalizations of Boxworld
• The chain rule implies Tsirelson's bound: an approach from generalized mutual information
• All tight correlation Bell inequalities have quantum violations
• Measurement uncertainty from no-signaling and non-locality
• Correlations constrained by composite measurements
• On the tightness of correlation inequalities with no quantum violation
• Experimental Distillation of Quantum Nonlocality
• Distillation of Multi-Party Non-Locality With and Without Partial Communication
• Multi-User Non-Locality Amplification
• Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise
• No-signaling bounds for quantum cloning and metrology
• Information Causality and Noisy Computations
• Quantum measurement of spins and magnets, and the classical limit of PR-boxes
• Verification of Bell Nonlocality by Violating Quantum Monogamy Relations
• Tsirelson's Bound Prohibits Communication Through a Disconnected Channel
• Estimation independence as an axiom for quantum uncertainty
• Why the Tsirelson bound?
• Scalable & Noise-Robust Communication Advantage of Multipartite Quantum Entanglement
• Random access test as an identifier of nonclassicality
• Three-input Majority Function as the Unique Optimal Function for the Bias Amplification using Nonlocal Boxes
• No Strong Parallel Repetition with Entangled and Non-signaling Provers
• Probing the limits of quantum theory with quantum information at subnuclear scales
• Tsirelson bounds for quantum correlations with indefinite causal order
• All two-party facet Bell inequalities are violated by Almost Quantum correlations
• Quaternionic quantum mechanics allows non-local boxes
• A Post-Quantum Associative Memory
• Classification of no-signaling correlations and the guess your neighbor's input game
• Computability limits non-local correlations
• Composing decoherence functionals
• Arbitrarily little knowledge can give a quantum advantage for nonlocal tasks
• Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH
• Quantum correlations cannot be reproduced with a finite number of measurements in any no-signaling theory
• Stabilizer states and local realism
• Trading Permutation Invariance for Communication in Multi-Party Non-Locality Distillation
• Algebra of Nonlocal Boxes and the Collapse of Communication Complexity
• Entanglement-swapping in generalised probabilistic theories, and iterated CHSH games
• Local hidden variable values without optimization procedures
• (Almost-)Quantum Bell Inequalities and Device-Independent Applications
• Quantum advantage for distributed computing without communication
• Remarks on the tensor product structure of no-signaling theories
• Classical-to-quantum non-signalling boxes
• Limitations imposed by complementarity
• Indefinite global time
• Characterization of non-signaling correlations from mutual information
• Quantum Computation and Arrows of Time