Perfect non-local quantum computation is impossible

Abstract

Non-local quantum computation (NLQC) asks two parties to apply a joint operation to their quantum inputs using an entangled resource state and one round of simultaneous quantum communication. NLQC has applications across quantum information, including attacks on quantum position verification, communication complexity, and quantum gravity. Every bipartite unitary has an approximate NLQC protocol with finite entanglement, and exact protocols are known for several structured families. However, it has remained open whether every fixed unitary admits an exact protocol with finite-dimensional resources. We show that, even for two qubits, Haar-almost every unitary does not admit such a protocol, even when the resource state and local operations are tailored to the target. The proof first shows that smooth deformations of an exact protocol can only change its target by local unitaries. For a fixed architecture, semialgebraic geometry limits the exact protocols to finitely many connected families, so each architecture reaches only finitely many local-unitary orbits. Taking the union over all architectures, the exactly implementable unitaries form countably many local-unitary orbits. We also show that some natural targets do not admit a protocol: the controlled phase diag(1,1,1,e^iθ) has no exact protocol with finite-dimensional resources whenever e^iθ is transcendental, for instance for θ= 1. Our results also apply to localizable quantum measurements, whose outcome is obtained from local measurements on inputs and a shared entangled resource state without communication. A rank-one projective measurement in a Haar-random basis is almost surely not localizable with a finite-dimensional resource state and finitely many local outcomes.

Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder
Yugo Takada, Hayata Yamasaki
npj Quantum Information1 Jul 2026Peer-reviewedCC BYFull textQuantum physics & quantum informationDOAJ
Entanglement cost in non-local quantum computation
Alex May
arXiv15 Sep 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Local decoders for fault-tolerant quantum computation and translation-invariant stabilizer codes
Nathaniel Selub, Aditya Bhardwaj, Ethan Lake
arXiv2 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum information Statistical & nonlinear physicsarXiv
Impossible to conjugate or reflect an unknown quantum state via a unitary evolution
Dafa Li
arXiv21 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Local energetic coupling enhances the expressivity of chemical computation
Marco Tuccio, Jason W. Rocks, Joshua E. Goldford
arXiv15 Sep 2026PreprintCC BY-NC-ND 4.0Full textSystems & synthetic biology Physical chemistryarXiv

Cite

BibTeX RIS

BibTeX

@misc{folkertsma2026perfect,
  title = {{Perfect non-local quantum computation is impossible}},
  author = {Marten Folkertsma and Dmitry Grinko and Gina Muuss and Florian Speelman},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40228},
  eprint = {2609.40228},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40228},
}

RIS

TY  - UNPB
TI  - Perfect non-local quantum computation is impossible
AU  - Marten Folkertsma
AU  - Dmitry Grinko
AU  - Gina Muuss
AU  - Florian Speelman
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40228
UR  - https://arxiv.org/abs/2609.40228
AB  - Non-local quantum computation (NLQC) asks two parties to apply a joint operation to their quantum inputs using an entangled resource state and one round of simultaneous quantum communication. NLQC has applications across quantum information, including attacks on quantum position verification, communication complexity, and quantum gravity. Every bipartite unitary has an approximate NLQC protocol with finite entanglement, and exact protocols are known for several structured families. However, it has remained open whether every fixed unitary admits an exact protocol with finite-dimensional resources. We show that, even for two qubits, Haar-almost every unitary does not admit such a protocol, even when the resource state and local operations are tailored to the target. The proof first shows that smooth deformations of an exact protocol can only change its target by local unitaries. For a fixed architecture, semialgebraic geometry limits the exact protocols to finitely many connected families, so each architecture reaches only finitely many local-unitary orbits. Taking the union over all architectures, the exactly implementable unitaries form countably many local-unitary orbits. We also show that some natural targets do not admit a protocol: the controlled phase diag(1,1,1,e^iθ) has no exact protocol with finite-dimensional resources whenever e^iθ is transcendental, for instance for θ= 1. Our results also apply to localizable quantum measurements, whose outcome is obtained from local measurements on inputs and a shared entangled resource state without communication. A rank-one projective measurement in a Haar-random basis is almost surely not localizable with a finite-dimensional resource state and finitely many local outcomes.
ER  -

Abstract

Related

Cite