  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.
