skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: The Round Complexity of Local Operations and Classical Communication (LOCC) in Random-Party Entanglement Distillation
A powerful operational paradigm for distributed quantum information processing involves manipulating pre-shared entanglement by local operations and classical communication (LOCC). The LOCC round complexity of a given task describes how many rounds of classical communication are needed to complete the task. Despite some results separating one-round versus two-round protocols, very little is known about higher round complexities. In this paper, we revisit the task of one-shot random-party entanglement distillation as a way to highlight some interesting features of LOCC round complexity. We first show that for random-party distillation in three qubits, the number of communication rounds needed in an optimal protocol depends on the entanglement measure used; for the same fixed state some entanglement measures need only two rounds to maximize whereas others need an unbounded number of rounds. In doing so, we construct a family of LOCC instruments that require an unbounded number of rounds to implement. We then prove explicit tight lower bounds on the LOCC round number as a function of distillation success probability. Our calculations show that the original W-state random distillation protocol by Fortescue and Lo is essentially optimal in terms of round complexity.  more » « less
Award ID(s):
2016136
PAR ID:
10505900
Author(s) / Creator(s):
; ;
Publisher / Repository:
Quantum
Date Published:
Journal Name:
Quantum
Volume:
7
ISSN:
2521-327X
Page Range / eLocation ID:
1104
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Reports on Progress in Physics)
    Abstract Secret-key distillation from quantum states and channels is a central task of interest in quantum information theory, as it facilitates private communication over a quantum network. Here, we study the task of secret-key distillation from bipartite states and point-to-point quantum channels using local operations and one-way classical communication (one-way LOCC). We employ the resource theory of unextendible entanglement to study the transformation of a bipartite state under one-way LOCC, and we obtain several efficiently computable upper bounds on the number of secret bits that can be distilled from a bipartite state using one-way LOCC channels; these findings apply not only in the one-shot setting but also in some restricted asymptotic settings. We extend our formalism to private communication over a quantum channel assisted by forward classical communication. We obtain efficiently computable upper bounds on the one-shot forward-assisted private capacity of a channel, thus addressing a question in the theory of quantum-secured communication that has been open for some time now. Our formalism also provides upper bounds on the rate of private communication when using a large number of channels in such a way that the error in the transmitted private data decreases exponentially with the number of channel uses. Moreover, our bounds can be computed using semidefinite programs, thus providing a computationally feasible method to understand the limits of private communication over a quantum network. 
    more » « less
  2. ; ; (, Springer Nature)
    Common random string model is a popular model in classi- cal cryptography. We study a quantum analogue of this model called the common Haar state (CHS) model. In this model, every party participating in the cryptographic system receives many copies of one or more i.i.d Haar random states. We study feasibility and limitations of cryptographic primitives in this model and its variants: ā€“ We present a construction of pseudorandom function-like states with security against computationally unbounded adversaries, as long as the adversaries only receive (a priori) bounded number of copies. By suitably instantiating the CHS model, we obtain a new approach to construct pseudorandom function-like states in the plain model. ā€“ We present separations between pseudorandom function-like states (with super-logarithmic length) and quantum cryptographic primitives, such as interactive key agreement and bit commitment, with classical communication. To show these separations, we prove new results on the indistinguishability of identical versus independent Haar states against LOCC (local operations, classical communication) adversaries. 
    more » « less
  3. ; ; (, PRX Quantum)
    Entanglement is essential for quantum information processing, but is limited by noise. We address this by developing high-yield entanglement distillation protocols with several advancements. (1) We extend the 2-to-1 recurrence entanglement distillation protocol to higher-rate n-to-(nāˆ’1) protocols that can correct any single-qubit errors. These protocols are evaluated through numerical simulations focusing on fidelity and yield. We also outline a method to adapt any classical error-correcting code for entanglement distillation, where the code can correct both bit-flip and phase-flip errors by incorporating Hadamard gates. (2) We propose a constant-depth decoder for stabilizer codes that transforms logical states into physical ones using single-qubit measurements. This decoder is applied to entanglement distillation protocols, reducing circuit depth and enabling protocols derived from high-performance quantum error-correcting codes. We demonstrate this by evaluating the circuit complexity for entanglement distillation protocols based on surface codes and quantum convolutional codes. (3) Our stabilizer entanglement distillation techniques advance quantum computing. We propose a fault-tolerant protocol for constant-depth encoding and decoding of arbitrary states in surface codes, with potential extensions to more general quantum low-density parity-check codes. This protocol is feasible with state-of-the-art reconfigurable atom arrays and surpasses the limits of conventional logarithmic depth encoders. Overall, our study integrates stabilizer formalism, measurement-based quantum computing, and entanglement distillation, advancing both quantum communication and computing. 
    more » « less
  4. ; ; (, New Journal of Physics)
    Abstract Entanglement is a striking feature of quantum mechanics, and it has a key property called unextendibility. In this paper, we present a framework for quantifying and investigating the unextendibility of general bipartite quantum states. First, we define the unextendible entanglement, a family of entanglement measures based on the concept of a state-dependent set of free states. The intuition behind these measures is that the more entangled a bipartite state is, the less entangled each of its individual systems is with a third party. Second, we demonstrate that the unextendible entanglement is an entanglement monotone under two-extendible quantum operations, including local operations and one-way classical communication as a special case. Normalization and faithfulness are two other desirable properties of unextendible entanglement, which we establish here. We further show that the unextendible entanglement provides efficiently computable benchmarks for the rate of exact entanglement or secret key distillation, as well as the overhead of probabilistic entanglement or secret key distillation. 
    more » « less
  5. ; ; ; (, CRYPTO 2023 conference proceedgins)
    SPRINGER (Ed.)
    In this work we study the problem of minimizing the round complexity for securely evaluating multiparty functionalities while making black-box use of polynomial time assumptions. In Eurocrypt 2016, Garg et al. showed that assuming all parties have access to a broadcast channel, then at least four rounds of communication are required to securely realize non-trivial functionalities in the plain model. A sequence of works follow-up the result of Garg et al. matching this lower bound under a variety of assumptions. Unfortunately, none of these works make black-box use of the underlying cryptographic primitives. In Crypto 2021, Ishai, Khurana, Sahai, and Srinivasan came closer to matching the four-round lower bound, obtaining a five-round protocol that makes black-box use of oblivious transfer and PKE with pseudorandom public keys. In this work, we show how to realize any input-less functionality (e.g., coin-tossing, generation of key-pairs, and so on) in four rounds while making black-box use of two-round oblivious transfer. As an additional result, we construct the first four-round MPC protocol for generic functionalities that makes black-box use of the underlying primitives, achieving security against non-aborting adversaries. Our protocols are based on a new primitive called list two-party computation. This primitive offers relaxed security compared to the standard notion of secure two-party computation. Despite this relaxation, we argue that this tool suffices for our applications. List two-party computation is of independent interest, as we argue it can also be used for the generation of setups, like oblivious transfer correlated randomness, in three rounds. Prior to our work, generating such a setup required at least four rounds of interactions or a trusted third party. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email