Quantum advantage for distributed computing without communication
arXiv:1408.0993 · doi:10.1103/PhysRevA.92.032122
Abstract
Understanding the role that quantum entanglement plays as a resource in various information processing tasks is one of the crucial goals of quantum information theory. Here we propose a new perspective for studying quantum entanglement: distributed computation of functions without communication between nodes. To formalize this approach, we propose identity games. Surprisingly, despite of no-signaling, we obtain that non-local quantum strategies beat classical ones in terms of winning probability for identity games originating from certain bipartite and multipartite functions. Moreover we show that, for majority of functions, access to general non-signaling resources boosts success probability two times in comparison to classical ones, for number of outputs large enough.
arXiv comment8 pages, 1 figure
References in corpus (19)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Bell nonlocality
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Non-locality and Communication Complexity
- Bounding the set of quantum correlations
- A Relevant Two Qubit Bell Inequality Inequivalent to the CHSH Inequality
- Randomness vs Non Locality and Entanglement
- Testing the Hilbert space dimension
- Local orthogonality as a multipartite principle for quantum correlations
- Guess your neighbour's input: a multipartite non-local game with no quantum advantage
- No quantum advantage for nonlocal computation
- Extremal correlations of the tripartite no-signaling polytope
- Quantum correlations require multipartite information principles
- Quantum Bounds on Bell inequalities
- Looking for symmetric Bell inequalities
- Partial list of bipartite Bell inequalities with four binary settings
- Lower bounds on information complexity via zero-communication protocols and applications
- Characterization of quantum correlations with local dimension constraints and its device-independent applications
- Closed sets of correlations: answers from the zoo