The aim of position-based cryptography is to use the geographical position of a party as its only credential. In this work,
we study position-based cryptography in the quantum setting.
We show that if collaborating adversaries are allowed
to pre-share an arbitrarily large entangled quantum state, then position-verification, and as a consequence position-based
cryptography in general, is impossible (also) in the quantum setting.
To this end, we prove that with the help of
sufficient pre-shared entanglement, any non-local quantum computation, i.e., any computation that involves quantum inputs
from two parties at different locations, can be performed instantaneously and without any communication, up to local corrections
that need to be applied to the outputs. The latter can be understood in that the parties obtain their respective outputs "encrypted",
where each corresponding encryption key is known by the opposite party. This result generalizes to any number of parties,
and it implies that any non-local quantum computation can be performed using a single round of mutual communication (in which
the parties exchange the encryption keys), and that any position-verification scheme can be broken, assuming sufficient pre-shared
entanglement among the adversaries.
On the positive side, we show that for adversaries that are restricted to not
share any entangled quantum states, secure position-verification is achievable. Jointly, these results suggest the interesting
question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result
can be interpreted as resolving this question in the simplest case, where the bound is set to zero.