Replacing Interaction with Entanglement
Alvin and I have recently completed a study of instantaneous nonlocal computation. This is a task – with a somewhat misleading name – that involves simulating a nonlocal quantum gate using pre-shared entanglement and non-interactive entanglement. One prominent application of this task is in quantum position verification, where the spatial coordinates of some individual can be certified using a time-constrained quantum computation. The time constraint prohibits any sort of interactive communication between potential adversaries trying to crack the verification scheme. We show that in general the number of ebits needed for the adversaries to succeed scales proportional to the size of the computation, even when just two ebits would suffice if interactive communication were allowed.