Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation
arXiv:1512.04930 · doi:10.1103/PhysRevA.94.022318
Abstract
In instantaneous nonlocal quantum computation, two parties cooperate in order to perform a quantum computation on their joint inputs, while being restricted to a single round of simultaneous communication. Previous results showed that instantaneous nonlocal quantum computation is possible, at the cost of an exponential amount of prior shared entanglement (in the size of the input). Here, we show that a linear amount of entanglement suffices, (in the size of the computation), as long as the parties share nonlocal correlations as given by the Popescu-Rohlich box. This means that communication is not required for efficient instantaneous nonlocal quantum computation. Exploiting the well-known relation to position-based cryptography, our result also implies the impossibility of secure position-based cryptography against adversaries with non-signalling correlations. Furthermore, our construction establishes a quantum analogue of the classical communication complexity collapse under non-signalling correlations.
arXiv comment4 pages, 2 figures. V2: new title, additional references
References in corpus (25)
- Quantum Teleportation is a Universal Computational Primitive
- Information Causality as a Physical Principle
- Non-local correlations as an information theoretic resource
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- A limit on nonlocality in any world in which communication complexity is not trivial
- Methodology for quantum logic gate constructions
- A glance beyond the quantum model
- Local orthogonality as a multipartite principle for quantum correlations
- Almost quantum correlations
- Quantum computing on encrypted data
- Unified derivations of measurement-based schemes for quantum computation
- Simplified instantaneous non-local quantum computation with applications to position-based cryptography
- Non-locality distillation and post-quantum theories with trivial communication complexity
- Recovering part of the quantum boundary from information causality
- Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints
- Position-Based Quantum Cryptography: Impossibility and Constructions
- Location-Dependent Communications using Quantum Entanglement
- Insecurity of position-based quantum cryptography protocols against entanglement attacks
- Macroscopically local correlations can violate information causality
- Delegating Private Quantum Computations
- Exploring the Local Orthogonality Principle
- On the power of non-local boxes
- Practical Position-Based Quantum Cryptography
- Quantum Location Verification in Noisy Channels
Cited by in corpus (6)
- Asymptotic performance of port-based teleportation
- Postquantum common-cause channels: the resource theory of local operations and shared entanglement
- Bounds on Instantaneous Nonlocal Quantum Computation
- Relating non-local quantum computation to information theoretic cryptography
- Universal resources for quantum computing
- Quantum homomorphic encryption for polynomial-sized circuits