Bounds on Instantaneous Nonlocal Quantum Computation
arXiv:1810.00994 · doi:10.1109/TIT.2019.2950190
Abstract
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 entangled bits (ebits). This offers an exponential improvement over the best known two-qubit protocols, whose ebit costs behave as . We also consider the family of binary controlled gates on dimensions . 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 ebits is shown in the case of generic (i.e. non-hermitian) gates from this family, even when . 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 commentComments welcome!
References in corpus (31)
- Quantum entanglement
- Concentrating Partial Entanglement by Local Operations
- Entanglement of a Pair of Quantum Bits
- Optimal Quantum Circuits for General Two-Qubit Gates
- Optimal Creation of Entanglement Using a Two--Qubit Gate
- Thermodynamics and the Measure of Entanglement
- Optimal local implementation of non-local quantum gates
- Entangling operations and their implementation using a small amount of entanglement
- Asymptotic teleportation scheme as a universal programmable quantum processor
- The non-local content of quantum operations
- On the capacities of bipartite Hamiltonians and unitary gates
- Optimizing practical entanglement distillation
- A Monogamy-of-Entanglement Game With Applications to Device-Independent Quantum Cryptography
- Simplified instantaneous non-local quantum computation with applications to position-based cryptography
- Quantum teleportation scheme by selecting one of multiple output ports
- Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints
- Instantaneous measurement of non-local variables
- Position-Based Quantum Cryptography: Impossibility and Constructions
- Location-Dependent Communications using Quantum Entanglement
- Insecurity of position-based quantum cryptography protocols against entanglement attacks
- Three maximally entangled states can require two-way LOCC for local discrimination
- Local Transformations Requiring Infinite Rounds of Classical Communication
- Practical Position-Based Quantum Cryptography
- Entanglement cost of implementing controlled-unitary operations
- Entanglement requirements for implementing bipartite unitary operations
- Entanglement consumption of instantaneous nonlocal quantum measurements
- Round Complexity in the Local Transformations of Quantum and Classical States
- Complexity of causal order structure in distributed quantum information processing and its trade-off with entanglement
- The Garden-Hose Model
- Fast protocols for local implementation of bipartite nonlocal unitaries
- Popescu-Rohrlich correlations imply efficient instantaneous nonlocal quantum computation
Cited by in corpus (12)
- Random-Receiver Quantum Communication
- A single-qubit position verification protocol that is secure against multi-qubit attacks
- Universal resources for quantum computing
- Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers
- Classification of joint quantum measurements based on entanglement cost of localization
- Towards a measurement theory in QFT: "Impossible" quantum measurements are possible but not ideal
- The Round Complexity of Local Operations and Classical Communication (LOCC) in Random-Party Entanglement Distillation
- Linear gate bounds against natural functions for position-verification
- Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss
- Teleportation of Post-Selected Quantum States
- Continuous-variable Quantum Position Verification secure against entangled attackers
- Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography