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:1101.1065 · New Journal of Physics

Simplified instantaneous non-local quantum computation with applications to position-based cryptography

Salman Beigi, Robert König

Published Sep 26, 2011• 144 citations
arXivHTMLPDF

Abstract

Instantaneous measurements of non-local observables between space-like separated regions can be performed without violating causality. This feat relies on the use of entanglement. Here we propose novel protocols for this task and the related problem of multipartite quantum computation with local operations and a single round of classical communication. Compared to previously known techniques, our protocols reduce the entanglement consumption by an exponential amount. We also prove a linear lower bound on the amount of entanglement required for the implementation of a certain non-local measurement. These results relate to position-based cryptography: an amount of entanglement scaling exponentially with the number of communicated qubits is sufficient to render any such scheme insecure. Furthermore, we show that certain schemes are secure under the assumption that the adversary has less entanglement than a given bound and is restricted to classical communication.

DOI
10.1088/1367-2630/13/9/093036

Related papers

Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits

Florian Speelman

Instantaneous non-local quantum computation requires multiple parties to jointly perform a quantum operation, using pre-shared entanglement and a single round of simultaneous communication. We study this task for its close connection to position-based quantum cryptography, but it also has natural applications in the context of foundations of quantum physics and in distributed computing. The best known general construction for instantaneous non-local quantum computation requires a pre-shared state which is exponentially large in the number of qubits involved in the operation, while efficient constructions are known for very specific cases only. We partially close this gap by presenting new schemes for efficient instantaneous non-local computation of several classes of quantum circuits, using the Clifford+T gate set. Our main result is a protocol which uses entanglement exponential in the T-depth of a quantum circuit, able to perform non-local computation of quantum circuits with a (poly-)logarithmic number of layers of T gates with quasi-polynomial entanglement. Our proofs combine ideas from blind and delegated quantum computation with the garden-hose model, a combinatorial model of communication complexity which was recently introduced as a tool for studying certain schemes for quantum position verification. As an application of our results, we also present an efficient attack on a recently-proposed scheme for position verification by Chakraborty and Leverrier.

arXiv:1511.02839•Leibniz international proceedings in informatics•Nov 9, 2015•40 citations

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•3 citations

Bounds on Instantaneous Nonlocal Quantum Computation

Alvin Gonzales, Eric Chitambar

Instantaneous nonlocal quantum computation refers to a process in which spacelike separated parties simulate a nonlocal quantum operation on their joint systems through the consumption of pre-shared entanglement. To prevent a violation of causality, this simulation succeeds up to local errors that can only be corrected after the parties communicate classically with one another. However, this communication is non-interactive, and it involves just the broadcasting of local measurement outcomes. We refer to this operational paradigm as local operations and broadcast communication (LOBC) to distinguish it from the standard local operations and (interactive) classical communication (LOCC). In this paper, we show that an arbitrary two-qubit gate can be implemented by LOBC with ϵ-error using O(log(1/ϵ)) entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as O(1/ϵ). We also consider the family of binary controlled gates on dimensions dA⊗ dB. We find that any hermitian gate of this form can be implemented by LOBC using a single shared ebit. In sharp contrast, a lower bound of log dB ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when dA= 2. This demonstrates an unbounded gap between the entanglement costs of LOCC and LOBC gate implementation. Whereas previous lower bounds on the entanglement cost for instantaneous nonlocal computation restrict the minimum dimension of the needed entanglement, we bound its entanglement entropy. To our knowledge this is the first such lower bound of its kind.

arXiv:1810.00994•IEEE Transactions on Information Theory•Oct 29, 2019•24 citations

Position-Based Quantum Cryptography: Impossibility and Constructions

Harry Buhrman, Nishanth Chandran, Serge Fehr +4 more

In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, the task of secure position-verification is impossible. To this end, we prove the following very general result. Assume that Alice and Bob hold respectively subsystems $A$ and $B$ of a (possibly) unknown quantum state $|\psi\rangle \in {\cal H}_A \otimes {\cal H}_B$. Their goal is to calculate and share a new state $|\varphi\rangle = U|\psi\rangle$, where $U$ is a fixed unitary operation. The question that we ask is how many rounds of mutual communication are needed. It is easy to achieve such a task using two rounds of classical communication, whereas, in general, it is impossible with no communication at all. Surprisingly, in case Alice and Bob share enough entanglement to start with and we allow an arbitrarily small failure probability, we show that the same task can be done using a single round of classical communication in which Alice and Bob exchange two classical messages. Actually, we prove that a relaxed version of the task can be done with no communication at all, where the task is to compute instead a state $|\varphi'\rangle$ that coincides with $|\varphi\rangle = U|\psi\rangle$ up to local operations on $A$ and on $B$, which are determined by classical information held by Alice and Bob. The one-round scheme for the original task then follows as a simple corollary. We also show that these results generalize to more players. As a consequence, we show a generic attack that breaks any position-verification scheme. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure position-verification is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any preshared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.

arXiv:1009.2490•SIAM Journal on Computing•Jan 1, 2014•158 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•1 citation

Rank lower bounds on non-local quantum computation

Vahid R. Asadi, Eric Culf, Alex May

A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, $f$-routing and $f$-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification. We give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function $f(x,y)$ in terms of the rank of a matrix $g(x,y)$ whose entries are zero when $f(x,y)=0$, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of $f(x,y)$. Because of a relationship between $f$-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS.

arXiv:2402.18647•Feb 28, 2024•15 citations
Instantaneous measurements of non-local observables between space-like separated regions can be performed without violating causality. This feat relies on the use of entanglement. Here we propose novel protocols for this task and the related problem of multipartite quantum computation with local operations and a single round of classical communication. Compared to previously known techniques, our protocols reduce the entanglement consumption by an exponential amount. We also prove a linear lower bound on the amount of entanglement required for the implementation of a certain non-local measurement. These results relate to position-based cryptography: an amount of entanglement scaling exponentially with the number of communicated qubits is sufficient to render any such scheme insecure. Furthermore, we show that certain schemes are secure under the assumption that the adversary has less entanglement than a given bound and is restricted to classical communication.
Instantaneous non-local quantum computation requires multiple parties to jointly perform a quantum operation, using pre-shared entanglement and a single round of simultaneous communication. We study this task for its close connection to position-based quantum cryptography, but it also has natural applications in the context of foundations of quantum physics and in distributed computing. The best known general construction for instantaneous non-local quantum computation requires a pre-shared state which is exponentially large in the number of qubits involved in the operation, while efficient constructions are known for very specific cases only. We partially close this gap by presenting new schemes for efficient instantaneous non-local computation of several classes of quantum circuits, using the Clifford+T gate set. Our main result is a protocol which uses entanglement exponential in the T-depth of a quantum circuit, able to perform non-local computation of quantum circuits with a (poly-)logarithmic number of layers of T gates with quasi-polynomial entanglement. Our proofs combine ideas from blind and delegated quantum computation with the garden-hose model, a combinatorial model of communication complexity which was recently introduced as a tool for studying certain schemes for quantum position verification. As an application of our results, we also present an efficient attack on a recently-proposed scheme for position verification by Chakraborty and Leverrier.
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.
Instantaneous nonlocal quantum computation refers to a process in which spacelike separated parties simulate a nonlocal quantum operation on their joint systems through the consumption of pre-shared entanglement. To prevent a violation of causality, this simulation succeeds up to local errors that can only be corrected after the parties communicate classically with one another. However, this communication is non-interactive, and it involves just the broadcasting of local measurement outcomes. We refer to this operational paradigm as local operations and broadcast communication (LOBC) to distinguish it from the standard local operations and (interactive) classical communication (LOCC). In this paper, we show that an arbitrary two-qubit gate can be implemented by LOBC with ϵ-error using O(log(1/ϵ)) entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as O(1/ϵ). We also consider the family of binary controlled gates on dimensions dA⊗ dB. We find that any hermitian gate of this form can be implemented by LOBC using a single shared ebit. In sharp contrast, a lower bound of log dB ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when dA= 2. This demonstrates an unbounded gap between the entanglement costs of LOCC and LOBC gate implementation. Whereas previous lower bounds on the entanglement cost for instantaneous nonlocal computation restrict the minimum dimension of the needed entanglement, we bound its entanglement entropy. To our knowledge this is the first such lower bound of its kind.
In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, the task of secure position-verification is impossible. To this end, we prove the following very general result. Assume that Alice and Bob hold respectively subsystems AAA and BBB of a (possibly) unknown quantum state ∣ψ⟩∈HA⊗HB|\psi\rangle \in {\cal H}_A \otimes {\cal H}_B∣ψ⟩∈HA​⊗HB​. Their goal is to calculate and share a new state ∣φ⟩=U∣ψ⟩|\varphi\rangle = U|\psi\rangle∣φ⟩=U∣ψ⟩, where UUU is a fixed unitary operation. The question that we ask is how many rounds of mutual communication are needed. It is easy to achieve such a task using two rounds of classical communication, whereas, in general, it is impossible with no communication at all. Surprisingly, in case Alice and Bob share enough entanglement to start with and we allow an arbitrarily small failure probability, we show that the same task can be done using a single round of classical communication in which Alice and Bob exchange two classical messages. Actually, we prove that a relaxed version of the task can be done with no communication at all, where the task is to compute instead a state ∣φ′⟩|\varphi'\rangle∣φ′⟩ that coincides with ∣φ⟩=U∣ψ⟩|\varphi\rangle = U|\psi\rangle∣φ⟩=U∣ψ⟩ up to local operations on AAA and on BBB, which are determined by classical information held by Alice and Bob. The one-round scheme for the original task then follows as a simple corollary. We also show that these results generalize to more players. As a consequence, we show a generic attack that breaks any position-verification scheme. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure position-verification is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any preshared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.
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 non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, fff-routing and fff-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification. We give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function f(x,y)f(x,y)f(x,y) in terms of the rank of a matrix g(x,y)g(x,y)g(x,y) whose entries are zero when f(x,y)=0f(x,y)=0f(x,y)=0, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of f(x,y)f(x,y)f(x,y). Because of a relationship between fff-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS.