Equivalence of non-local computation tasks beyond Clifford operations
Abstract
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=C1DC0 with D an arbitrary diagonal unitary and C0, C1 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.
Related
- Local Clifford equivalence to CSS codes: Polynomial-time classification and conversion
- Modular optical fault-tolerant quantum computation via an interface between verified resources and online logical operations
- From Syndromes to Computation: A General Framework for Logical Operations in Quantum Error-Correcting Codes
- Polynomial equivalence of the global transverse-field Ising model and the gate model of quantum computation
- The Fer expansion of a driven spin under su(2) operations cannot terminate beyond first order
BibTeX
@misc{bluhm2026equivalence,
title = {{Equivalence of non-local computation tasks beyond Clifford operations}},
author = {Andreas Bluhm and Simon Höfer and Alex May and Florian Speelman and Philip Verduyn Lunel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.26354},
eprint = {2606.26354},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.26354},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Equivalence of non-local computation tasks beyond Clifford operations
AU - Andreas Bluhm
AU - Simon Höfer
AU - Alex May
AU - Florian Speelman
AU - Philip Verduyn Lunel
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2606.26354
UR - https://arxiv.org/abs/2606.26354
AB - 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.
ER -