Curator's Take
This article shows that seemingly modest non‑local computation primitives—such as a single‑round “redirect” task with classical control—can be leveraged to implement far more powerful operations, including arbitrary Clifford gates and controlled unitaries of the form C₁DC₀, thereby exposing a hidden hierarchy among NLQC tasks. By mapping these reductions, the work clarifies which position‑verification protocols are fundamentally hard or easy to break, tightening security analyses that have long relied on heuristic arguments. The results also tighten the bridge between quantum communication complexity and emerging ideas in quantum gravity, suggesting new avenues for both practical protocol design and theoretical exploration.
— Mark Eatherly
Summary
Non-local quantum computation (NLQC) studies how two collaborating players can implement channels on distributed systems using a single simultaneous round of quantum communication and shared entanglement. NLQC has applications in diverse areas, ranging from quantum position-verification to quantum gravity. Recently, it has been realized that the relationships among families of NLQC tasks are highly structured: many seemingly distinct tasks are related by reductions, wherein implementations of one task can be used to efficiently implement a second task. This is analogous to the notion of reduction in complexity theory, and reveals the relative hardness of NLQC tasks. In this work we continue the study of reductions among NLQC tasks. We focus on NLQC examples of the greatest interest in quantum position-verification; in particular examples involving large classical inputs and fixed-size quantum inputs, since these constitute the most feasible protocols for position-verification schemes. Within this setting, we find many new relationships among NLQC tasks. For instance, protocols for the simplest example of redirecting a quantum system based on a classical control imply protocols for controlled single qubit measurements in arbitrary bases, the controlled application of any Clifford unitary, and even the controlled application of any unitary of the form $U=C_1DC_0$ with $D$ an arbitrary diagonal unitary and $C_0, C_1$ Clifford circuits. This implies that many feasible position-verification schemes have the same asymptotic scaling for their entanglement cost, and hence a similar level of security. Our techniques rely on ideas from gate teleportation and measurement based quantum computation, among other areas, bringing several new strategies into NLQC which may be of independent interest.