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• 121 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

Non-signalling correlations imply efficient instantaneous nonlocal quantum computation

Anne Broadbent

In instantaneous nonlocal quantum computation, two parties cooperate in order to perform a quantum computation on their joint inputs, while being restricted to a single round of simultaneous communication. Previous results showed that instantaneous nonlocal quantum computation is possible, at the cost of an exponential amount of prior shared entanglement (in the size of the input). Here, we show that a linear amount of entanglement suffices, (in the size of the computation), as long as the parties share nonlocal correlations as given by the Popescu-Rohlich box. This means that communication is not required for efficient instantaneous nonlocal quantum computation. Exploiting the well-known relation to position-based cryptography, our result also implies the impossibility of secure position-based cryptography against adversaries with non-signalling correlations. Furthermore, our construction establishes a quantum analogue of the classical communication complexity collapse under non-signalling correlations.

•Dec 15, 2015•2 citations

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

Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation

Anne Broadbent

In instantaneous nonlocal quantum computation, two parties cooperate in order to perform a quantum computation on their joint inputs, while being restricted to a single round of simultaneous communication. Previous results showed that instantaneous nonlocal quantum computation is possible, at the cost of an exponential amount of prior shared entanglement (in the size of the input). Here, we show that a linear amount of entanglement suffices, (in the size of the computation), as long as the parties share nonlocal correlations as given by the Popescu-Rohrlich box. This means that communication is not required for efficient instantaneous nonlocal quantum computation. Exploiting the well-known relation to position-based cryptography, our result also implies the impossibility of secure position-based cryptography against adversaries with nonsignaling correlations. Furthermore, our construction establishes a quantum analog of the classical communication complexity collapse under nonsignaling correlations.

arXiv:1512.04930•Physical Review A•Aug 15, 2016•10 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•17 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
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.
In instantaneous nonlocal quantum computation, two parties cooperate in order to perform a quantum computation on their joint inputs, while being restricted to a single round of simultaneous communication. Previous results showed that instantaneous nonlocal quantum computation is possible, at the cost of an exponential amount of prior shared entanglement (in the size of the input). Here, we show that a linear amount of entanglement suffices, (in the size of the computation), as long as the parties share nonlocal correlations as given by the Popescu-Rohlich box. This means that communication is not required for efficient instantaneous nonlocal quantum computation. Exploiting the well-known relation to position-based cryptography, our result also implies the impossibility of secure position-based cryptography against adversaries with non-signalling correlations. Furthermore, our construction establishes a quantum analogue of the classical communication complexity collapse under non-signalling correlations.
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.
In instantaneous nonlocal quantum computation, two parties cooperate in order to perform a quantum computation on their joint inputs, while being restricted to a single round of simultaneous communication. Previous results showed that instantaneous nonlocal quantum computation is possible, at the cost of an exponential amount of prior shared entanglement (in the size of the input). Here, we show that a linear amount of entanglement suffices, (in the size of the computation), as long as the parties share nonlocal correlations as given by the Popescu-Rohrlich box. This means that communication is not required for efficient instantaneous nonlocal quantum computation. Exploiting the well-known relation to position-based cryptography, our result also implies the impossibility of secure position-based cryptography against adversaries with nonsignaling correlations. Furthermore, our construction establishes a quantum analog of the classical communication complexity collapse under nonsignaling correlations.
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.
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.