Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation

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.

4 pages, 2 figures. V2: new title, additional references

References in corpus (7)

• Instantaneous non-local computation of low T-depth quantum circuits
• Almost quantum correlations
• Non-locality distillation and post-quantum theories with trivial communication complexity
• Recovering part of the quantum boundary from information causality
• Location-Dependent Communications using Quantum Entanglement
• Insecurity of position-based quantum cryptography protocols against entanglement attacks
• Macroscopically local correlations can violate information causality

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