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.
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.
In this Letter, we investigate the number of measurement and communication rounds needed to implement certain tasks by local quantum operations and classical communication (LOCC), a relatively unexplored topic. To demonstrate the possible strong dependence on the round number, we consider the problem of converting three-qubit entanglement into two-qubit form, specifically in the random distillation setting of [Phys. Rev. Lett. 98, 260501 (2007)]. We find that the number of LOCC rounds needed for a transformation can depend on the amount of entanglement distilled. In fact, for a wide range of transformations, the required number of rounds is infinite (unbounded). This represents the first concrete example of a task needing an infinite number of rounds to implement.
Quantum entanglement distillation protocols are LOCC protocols that, over ``imperfect'' EPR pairs shared between Alice and Bob as input, output perfect or near-perfect EPR pairs. In this paper, we study the communication complexity of these protocols, that is, the minimal number of (classical) bits needed for Alice and Bob. To our knowledge, it is the first paper that studies entanglemend distillation protocols in the resource-bounded case. We consider 3 models for imperfect EPR pairs. In the measure-r model, r out of n EPR pairs are measured by an adversary (and thus become ``corrupted''); in the depolarization model, the qubits of Bob underwent a depolarization channel; in the fidelity model, the only information Alice and Bob possess is the fidelity of the shared state. For the first 2 models, we prove tight and almost-tight bounds on the base case, i.e., how well Alice and Bob can do if they are not allowed to communicate. For the fidelity model, we prove a very tight lower bound (up to an additive constant) on the communication complexity. This lower bound implies the optimality of the Random Hash protocol in [ASY02].
We prove that there is a trade-off relation between the entanglement cost and the number of rounds of communication, for two distant parties to accomplish a bidirectional quantum information task by local operations and classical communication (LOCC). We consider an implementation of a class of two-qubit controlled-unitary gate by LOCC assisted by shared entanglement, in an information theoretical scenario of asymptotically many input pairs and vanishingly small error. We prove the trade-off relation by showing that one ebit of entanglement per pair is necessary to be consumed for implementing the unitary by any two-round protocol, whereas the entanglement cost by a four-round protocol is strictly smaller than one ebit per pair.
Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the conversion. In this paper, we focus on the communication complexity of protocols that operate with incomplete information, i.e., where the inputs are mixed states and/or prepared adversarially. We consider three models of imperfect entanglement, namely, the bounded measurement model, the depolarization model, and the fidelity model. We describe these models as well as the motivations for studying them. For the bounded measurement model and the depolarization model, we prove tight and almost-tight bounds on the output quality of non-interactive protocols. For the fidelity model, we prove a lower bound that matches the upper bound given by Ambainis et al., and thus completely characterizes communication complexity of entanglement distillation protocols for this model. Our result also suggests the optimality of the BB84 protocol in terms of communication complexity. We emphasize that although some of the results appear intuitively straightforward, their proofs are not. In fact, two novel techniques are developed for proving these results. We believe that these techniques are of independent interests, too.
Given a protocol P that implements multipartite quantum channel E by repeated rounds of local operations and classical communication (LOCC), we construct an alternate LOCC protocol for E in no more rounds than P and no more than a fixed, constant number of outcomes for each local measurement, the same constant number for every party and every round. We then obtain another upper bound on the number of outcomes that, under certain conditions, improves on the first. The latter bound shows that for LOCC channels that are extreme points of the convex set of all quantum channels, the parties can restrict the number of outcomes in their individual local measurements to no more than the square of their local Hilbert space dimension, ${d}_{\ensuremath{\alpha}}$, suggesting a possible link between the required resources for LOCC and the convex structure of the set of all quantum channels. Our bounds on the number of outcomes indicating the need for only constant resources per round, independent of the number of rounds r including when that number is infinite, are a stark contrast to the exponential r dependence in the only previously published bound of which we are aware. If a lower bound is known on the number of product operators needed to represent the channel, we obtain a lower bound on the number of rounds required to implement the given channel by LOCC. Finally, we show that when the quantum channel is not required but only that a given task be implemented deterministically, then no more than ${d}_{\ensuremath{\alpha}}^{2}$ outcomes are needed for each local measurement by party $\ensuremath{\alpha}$.
In distributed quantum and classical information processing, spatially separated parties operate locally on their respective subsystems, but coordinate their actions through multiple exchanges of public communication. With interaction, the parties can perform more tasks. But how the exact number and order of exchanges enhances their operational capabilities is not well understood. Here we consider the minimum number of communication rounds needed to perform the locality-constrained tasks of entanglement transformation and its classical analog of secrecy manipulation. We provide an explicit construction of both quantum and classical state transformations which, for any given r, can be achieved using r rounds of classical communication exchanges, but no fewer. To show this, we build on the common structure underlying both resource theories of quantum entanglement and classical secret key. Our results reveal that highly complex communication protocols are indeed necessary to fully harness the information-theoretic resources contained in general quantum and classical states.