arXiv:2609.40228
Perfect non-local quantum computation is impossible
Marten Folkertsma, Dmitry Grinko, Gina Muuss, Florian Speelman
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 $\mathrm{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.
AI Summary
Non-local quantum computation (NLQC) asks whether two parties can implement a fixed bipartite operation using shared entanglement, local processing, and one simultaneous exchange of messages. Although every unitary admits finite-resource approximate protocols, the paper addresses whether every fixed unitary admits an exact protocol with finite-dimensional resources tailored to it. For each finite protocol architecture, the exactly implementable unitaries form finitely many equivalence classes under local-unitary pre- and post-processing. Across all finite architectures, they therefore form countably many such classes and have Haar measure zero, even for two-qubit targets. An explicit exclusion is the controlled-phase gate $C_\theta=\operatorname{diag}(1,1,1,e^{i\theta})$: exact finite-dimensional implementation requires $e^{i\theta}$ to be algebraic, ruling out $\theta=1$. An analogous finite-orbit theorem excludes exact two-sided implementation of Haar-random rank-one projective measurements, and consequently their localization using finite-dimensional entanglement and finitely many local outcomes. The proof uses input-independent discarded environments for exact unitary channels to show that smooth protocol deformations change the target only within its local-unitary orbit. Semialgebraic geometry supplies finitely many connected components per architecture. Rational-coefficient polynomial orbit invariants yield the explicit controlled-phase obstruction; outcome-dependent environment states support the measurement extension. The results concern zero error, not quantitative resource lower bounds for approximation or operational QPV security. They do not classify algebraic phases, settle implementation with infinite-Schmidt-rank resources of finite entanglement entropy or infinite-dimensional messages, or cover general channels and multipartite protocols.
helped explore proof strategies and draft and revise proofs. The exploration was human-guided towards various approaches and simplified versions of the problem, and the final successful proofs were contributed by the AI agents.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 29 pages, 2 figures