Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40228

Perfect non-local quantum computation is impossible

Marten Folkertsma, Dmitry Grinko, Gina Muuss, Florian Speelman

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

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.

Comments
29 pages, 2 figures

Related papers

Equivalence of non-local computation tasks beyond Clifford operations

Andreas Bluhm, Simon Höfer, Alex May +2 more

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.

quant-pharXiv:2606.26354•Jun 26, 2026•0 citations

Exponential lower bounds for low-degree strategies in position-based quantum cryptography

Isabel M. Moreno-Cuadrado, David Perez-Garcia, Carlos Palazuelos

Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary $U_{AB}$ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary $U_{AB}$ whose implementation in NLQC requires extra quantum systems with dimensions ${\rm exp}(n^{Ω(1)})$, where $n$ is the dimension of systems $A$ and $B$. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in $n$. In this paper we consider the family of diagonal ${\pm 1}$ valued unitaries $U_{\varepsilon}$, indexed by an element of the Boolean hypercube $\varepsilon \in \{\pm 1\}^{n^2}$, i.e. $U_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_B$. We show that if $U_{\varepsilon}$ can be implemented in NLQC with constant accuracy for all $\varepsilon$, and the dependency on $\varepsilon$ in the first round of the associated strategy is a polynomial of degree $O(n^{\frac{1}{4}-δ})$, then the implementation of at least one $U_{\varepsilon}$ in NLQC requires resources scaling as $\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)$. The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.

quant-pharXiv:2609.35592•Sep 29, 2026•0 citations

Finite Nonsignalling Resources Suffice to Simulate Entangled Qubits

Ziao Tang, Xin Wang, Ge Bai

A longstanding question in Bell nonlocality is whether finite-alphabet nonsignalling resources can reproduce the continuum of measurement correlations of partially entangled qubits. Here we resolve this problem by showing that every fixed pure two-qubit state admits an exact simulation of all local projective-measurement statistics using shared randomness and finitely many Popescu-Rohrlich (PR) boxes, without communication or postselection. The boxes operate in parallel, with a worst-case bound independent of the measurement settings: at most $128\cot^4θ$ calls for the Schmidt state $\cosθ|00\rangle+\sinθ|11\rangle$, $0<θ<π/4$. The key is an exact finite-selection method that reduces input-dependent continuous sampling to a choice from a fixed-length shared random list, implemented through a finite PR-box network. The construction extends to arbitrary mixed two-qubit states and local binary-outcome POVMs. This reveals a fundamental separation between the continuity of quantum measurement correlations and the alphabet size of the resources needed to simulate them, shedding light on the resource-theoretic structure of Bell nonlocality.

quant-pharXiv:2610.32319•Oct 26, 2026•0 citations

A complexity theory for non-local quantum computation

Andreas Blühm, Simon Höfer, Alex May +3 more

Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that f -measure and f -route, the two best studied NLQC tasks, are in fact equivalent under O ( 1 ) overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to f -measure. For instance, we obtain sub-exponential upper bounds on f -measure for all functions, and efficient protocols for functions in the complexity class M o d k L . Beyond this, we study a number of other examples of NLQC tasks and their relationships.

arXiv:2505.23893•Quantum•Jul 1, 2026•0 citations

Entanglement cost in non-local quantum computation

Alex May

This is a book-length treatment of the subject of non-local quantum computation (NLQC). NLQC is a method for implementing quantum operations that interact two systems without directly bringing the systems together. Instead, a single round of communication and shared entanglement is used. NLQC has appeared in the context of quantum cryptography, computational complexity, communication complexity, quantum gravity, and other applications. The understanding of entanglement cost in NLQC is closely tied to questions in all of these areas. We review upper and lower bounds on entanglement cost, as well as some of the applications of NLQC and its connections to other subjects.

quant-pharXiv:2605.02840•May 5, 2026•0 citations

Lower bounds on non-local computation from controllable correlation

Richard Cleve, Alex May

Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, $\sqrt{\text{SWAP}}$, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.

quant-pharXiv:2602.00255•Feb 3, 2026•0 citations
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,eiθ)\mathrm{diag}(1,1,1,e^{iθ})diag(1,1,1,eiθ) has no exact protocol with finite-dimensional resources whenever eiθe^{iθ}eiθ is transcendental, for instance for θ=1θ= 1θ=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.
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=C1DC0U=C_1DC_0U=C1​DC0​ with DDD an arbitrary diagonal unitary and C0,C1C_0, C_1C0​,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.
Non-local quantum computation (NLQC) consists on the implementation of a bipartite unitary UABU_{AB}UAB​ by two cooperating distant players by means of a two-round protocol with a single intermediate round of simultaneous communication. It is a major open question to know whether there exists a unitary UABU_{AB}UAB​ whose implementation in NLQC requires extra quantum systems with dimensions exp(nΩ(1)){\rm exp}(n^{Ω(1)})exp(nΩ(1)), where nnn is the dimension of systems AAA and BBB. This type of exponential lower bound is essential for security of position-based quantum cryptography, since the capabilities of the adversaries are precisely described by NLQC. It has also been connected to many other problems, such as the optimality of universal quantum simulators, or the expected properties of holographic quantum gravity. Currently the best lower bounds are only sublinear in nnn. In this paper we consider the family of diagonal ±1{\pm 1}±1 valued unitaries UεU_{\varepsilon}Uε​, indexed by an element of the Boolean hypercube ε∈{±1}n2\varepsilon \in \{\pm 1\}^{n^2}ε∈{±1}n2, i.e. Uε∣i⟩A∣j⟩B=εij∣i⟩A∣j⟩BU_{\varepsilon}|i\rangle_A|j\rangle_B =\varepsilon_{ij} |i\rangle_A|j\rangle_BUε​∣i⟩A​∣j⟩B​=εij​∣i⟩A​∣j⟩B​. We show that if UεU_{\varepsilon}Uε​ can be implemented in NLQC with constant accuracy for all ε\varepsilonε, and the dependency on ε\varepsilonε in the first round of the associated strategy is a polynomial of degree O(n14−δ)O(n^{\frac{1}{4}-δ})O(n41​−δ), then the implementation of at least one UεU_{\varepsilon}Uε​ in NLQC requires resources scaling as exp⁡(Ω(n2δ(log⁡n)2))\exp\left(Ω\left(\frac{n^{2δ}}{(\log n)^2}\right)\right)exp(Ω((logn)2n2δ​)). The proof is based on geometric properties of particular Banach spaces, namely their type constants, together with random estimates of Boolean functions valued on them.
A longstanding question in Bell nonlocality is whether finite-alphabet nonsignalling resources can reproduce the continuum of measurement correlations of partially entangled qubits. Here we resolve this problem by showing that every fixed pure two-qubit state admits an exact simulation of all local projective-measurement statistics using shared randomness and finitely many Popescu-Rohrlich (PR) boxes, without communication or postselection. The boxes operate in parallel, with a worst-case bound independent of the measurement settings: at most 128cot⁡4θ128\cot^4θ128cot4θ calls for the Schmidt state cos⁡θ∣00⟩+sin⁡θ∣11⟩\cosθ|00\rangle+\sinθ|11\ranglecosθ∣00⟩+sinθ∣11⟩, 0<θ<π/40<θ<π/40<θ<π/4. The key is an exact finite-selection method that reduces input-dependent continuous sampling to a choice from a fixed-length shared random list, implemented through a finite PR-box network. The construction extends to arbitrary mixed two-qubit states and local binary-outcome POVMs. This reveals a fundamental separation between the continuity of quantum measurement correlations and the alphabet size of the resources needed to simulate them, shedding light on the resource-theoretic structure of Bell nonlocality.
Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that f -measure and f -route, the two best studied NLQC tasks, are in fact equivalent under O ( 1 ) overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to f -measure. For instance, we obtain sub-exponential upper bounds on f -measure for all functions, and efficient protocols for functions in the complexity class M o d k L . Beyond this, we study a number of other examples of NLQC tasks and their relationships.
This is a book-length treatment of the subject of non-local quantum computation (NLQC). NLQC is a method for implementing quantum operations that interact two systems without directly bringing the systems together. Instead, a single round of communication and shared entanglement is used. NLQC has appeared in the context of quantum cryptography, computational complexity, communication complexity, quantum gravity, and other applications. The understanding of entanglement cost in NLQC is closely tied to questions in all of these areas. We review upper and lower bounds on entanglement cost, as well as some of the applications of NLQC and its connections to other subjects.
Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, SWAP\sqrt{\text{SWAP}}SWAP​, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.