Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation

Anne Broadbent
Phys. Rev. A 94, 022318 – Published 15 August 2016

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-Rohrlich 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 nonsignaling correlations. Furthermore, our construction establishes a quantum analog of the classical communication complexity collapse under nonsignaling correlations.

  • Figure
  • Figure
  • Received 7 January 2016

DOI:https://doi.org/10.1103/PhysRevA.94.022318

©2016 American Physical Society

Physics Subject Headings (PhySH)

General PhysicsQuantum Information, Science & TechnologyInterdisciplinary Physics

Authors & Affiliations

Anne Broadbent

  • Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario, Canada K1N 6N5

  • *abroadbe@uottawa.ca
  • Part of this research was performed while the author was affiliated with IQC, University of Waterloo.

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 94, Iss. 2 — August 2016

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×