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

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

Andris Ambainis, Ke Yang

Published Dec 29, 2008• 1 citation
OpenAlex

Abstract

Abstract Entanglement is an essential resource for quantum com-munication and quantum computation, similar to shared random bits in the classical world. Entanglement distil-lation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity ofthese protocols is the minimal amount of classical information that needs to be exchanged for the conversion. In thispaper, we focus on the communication complexity of protocols that operate with incomplete information, i.e., wherethe 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 there mod-els 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 weprove a lower bound that matches the upper bound given by Ambainis et al., and thus completely characterizes commu-nication complexity of entanglement distillation protocols for this model. Our result also suggests the optimality ofthe BB84 protocol in terms of communication complexity. We emphasize that although some of the results appearintuitively 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.

Related papers

Towards the classical communication complexity of entanglement distillation protocols with incomplete information

Andris Ambainis, Ke Yang

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.

IEEE Conference on Computational Complexity (CCC)•Nov 12, 2004•0 citations

Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

Andris Ambainis, Ke Yang

Quantum entanglement distillation protocols are LOCC protocols between Alice and Bob that convert imperfect EPR pairs, or, in general, partially entangled bipartite states into perfect or near-perfect EPR pairs. The classical communication complexity of these protocols is the minimal amount of classical communication needed 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 study 3 models of imperfect EPR pairs. In the measure-r model, r out of n EPR pairs are measured by an adversary; in the depolarization model, Bob's share of qubits underwent a depolarization channel; in the fidelity model, the only information Alice and Bob possess is the fidelity of the shared state. For the measure-r model and the depolarization model, we prove tight and almost-tight bounds on the outcome of LOCC protocols that don't use communication. For the fidelity model, we prove a lower bound on the communication complexity that matches the upper bound given by Ambainis, Smith, and Yang [ASY02].

arXiv:quant-ph/0207090•Jul 17, 2002•1 citation

Computational entanglement distillation beyond pure states: efficient protocols and fundamental limitations

Takeru Utsumi, Jacopo Rizzo, Ryuji Takagi +1 more

The information-theoretic approach to entanglement typically relies on arbitrarily many input copies and unboundedly complex operations; however, the available resources are constrained in reality. This motivates the study of entanglement theory with limited resources. One of its central questions is which quantities characterize entanglement manipulations, and so far, only the idealized case of pure states has been well explored. In this work, we address entanglement distillation from mixed states and identify the Rényi coherent information as the quantity determining the optimal rate in the worst case under two distinct resource constraints. We first characterize the sample-efficient regime, in which unbounded computational power is allowed. Our universal protocol achieves this rate without knowledge of the input state under certain polynomial rank constraints. This rate is optimal among universal protocols: we construct states whose distillable entanglement is nearly extensive, yet from which no universal sample-efficient protocol attains a rate above their Rényi coherent information. We then push this characterization to the computationally efficient frontier: the same bound holds for any efficient protocol even when the input state is known, and another universal protocol achieves this rate efficiently under additional polynomial constraints on the marginal ranks. Overall, our results give the Rényi coherent information a novel operational meaning in two computational settings: universal distillation with limited copies and efficient distillation even with knowledge of the input state.

quant-pharXiv:2610.06787•Oct 6, 2026•0 citations

Towards the Communication Complexity of Entanglement Distillation Protocols

Andris Ambainis, Ke Yang

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].

•Jul 17, 2002•0 citations

The Round Complexity of Local Operations and Classical Communication (LOCC) in Random-Party Entanglement Distillation

Guangkuo Liu, Ian M. George, Eric Chitambar

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.

arXiv:2204.00781•Quantum•Sep 7, 2023•4 citations

Tensor norms and the classical communication complexity of nonlocal quantum measurement

Yaoyun Shi

Nonlocality is at the heart of quantum information processing. In this paper we investigate the minimum amount of classical communication required to simulate a nonlocal quantum measurement. We derive general upper bounds, which in turn translate to systematic classical simulations of quantum communication protocols.As a concrete application, we prove that any quantum communication protocol with shared entanglement for computing a Boolean function can be simulated by a classical protocol whose cost does not depend on the amount of the shared entanglement. This implies that if the cost of communication is a constant, quantum and classical protocols, with shared entanglement and shared coins, respectively, compute the same class of functions.Furthermore, we describe a new class of efficient quantum communication protocols based on fast quantum algorithms. While some of them have efficient classical simulations by our method, others appear to be good candidates for separating quantum v.s. classical protocols, and quantum protocols with v.s. without shared entanglement.Yet another application is in the context of simulating quantum correlations using local hidden variable models augmented with classical communications. We give a constant cost, approximate simulation of quantum correlations when the number of correlated variables is a constant, while the dimension of the entanglement and the number of possible measurements can be arbitrary.Our upper bounds are expressed in terms of some tensor norms on the measurement operator. Those norms capture the nonlocality of bipartite operators in their own way and may be of independent interest and further applications.

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•5 citations
Abstract Entanglement is an essential resource for quantum com-munication and quantum computation, similar to shared random bits in the classical world. Entanglement distil-lation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity ofthese protocols is the minimal amount of classical information that needs to be exchanged for the conversion. In thispaper, we focus on the communication complexity of protocols that operate with incomplete information, i.e., wherethe 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 there mod-els 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 weprove a lower bound that matches the upper bound given by Ambainis et al., and thus completely characterizes commu-nication complexity of entanglement distillation protocols for this model. Our result also suggests the optimality ofthe BB84 protocol in terms of communication complexity. We emphasize that although some of the results appearintuitively 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.
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.
Quantum entanglement distillation protocols are LOCC protocols between Alice and Bob that convert imperfect EPR pairs, or, in general, partially entangled bipartite states into perfect or near-perfect EPR pairs. The classical communication complexity of these protocols is the minimal amount of classical communication needed 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 study 3 models of imperfect EPR pairs. In the measure-r model, r out of n EPR pairs are measured by an adversary; in the depolarization model, Bob's share of qubits underwent a depolarization channel; in the fidelity model, the only information Alice and Bob possess is the fidelity of the shared state. For the measure-r model and the depolarization model, we prove tight and almost-tight bounds on the outcome of LOCC protocols that don't use communication. For the fidelity model, we prove a lower bound on the communication complexity that matches the upper bound given by Ambainis, Smith, and Yang [ASY02].
The information-theoretic approach to entanglement typically relies on arbitrarily many input copies and unboundedly complex operations; however, the available resources are constrained in reality. This motivates the study of entanglement theory with limited resources. One of its central questions is which quantities characterize entanglement manipulations, and so far, only the idealized case of pure states has been well explored. In this work, we address entanglement distillation from mixed states and identify the Rényi coherent information as the quantity determining the optimal rate in the worst case under two distinct resource constraints. We first characterize the sample-efficient regime, in which unbounded computational power is allowed. Our universal protocol achieves this rate without knowledge of the input state under certain polynomial rank constraints. This rate is optimal among universal protocols: we construct states whose distillable entanglement is nearly extensive, yet from which no universal sample-efficient protocol attains a rate above their Rényi coherent information. We then push this characterization to the computationally efficient frontier: the same bound holds for any efficient protocol even when the input state is known, and another universal protocol achieves this rate efficiently under additional polynomial constraints on the marginal ranks. Overall, our results give the Rényi coherent information a novel operational meaning in two computational settings: universal distillation with limited copies and efficient distillation even with knowledge of the input state.
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-rrr model, rrr out of nnn 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].
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.
Nonlocality is at the heart of quantum information processing. In this paper we investigate the minimum amount of classical communication required to simulate a nonlocal quantum measurement. We derive general upper bounds, which in turn translate to systematic classical simulations of quantum communication protocols.As a concrete application, we prove that any quantum communication protocol with shared entanglement for computing a Boolean function can be simulated by a classical protocol whose cost does not depend on the amount of the shared entanglement. This implies that if the cost of communication is a constant, quantum and classical protocols, with shared entanglement and shared coins, respectively, compute the same class of functions.Furthermore, we describe a new class of efficient quantum communication protocols based on fast quantum algorithms. While some of them have efficient classical simulations by our method, others appear to be good candidates for separating quantum v.s. classical protocols, and quantum protocols with v.s. without shared entanglement.Yet another application is in the context of simulating quantum correlations using local hidden variable models augmented with classical communications. We give a constant cost, approximate simulation of quantum correlations when the number of correlated variables is a constant, while the dimension of the entanglement and the number of possible measurements can be arbitrary.Our upper bounds are expressed in terms of some tensor norms on the measurement operator. Those norms capture the nonlocality of bipartite operators in their own way and may be of independent interest and further applications.