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:quant-ph/0207090

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

Andris Ambainis, Ke Yang

Published Jul 17, 2002• 1 citation
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.quant-ph/0207090

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

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

Andris Ambainis, Ke Yang

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.

•Dec 29, 2008•1 citation

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

Bell-pair distillation under imperfect operations

András Kinyó, Tamás Kiss, Orsolya Kálmán

We recently proposed an entanglement distillation protocol based on local operations and classical communication that probabilistically and universally distills a maximally entangled Bell pair from multiple copies of an unknown two-qubit state [Phys. Rev. Lett. 135, 260202 (2025)]. Here, we investigate the robustness of this protocol against imperfections in its implementation. We consider several incoherent and coherent gate-error models, as well as measurement readout errors, and determine the regimes in which distillation enhances the fidelity with the target Bell state. We find that the protocol remains effective over substantial error ranges, although its robustness depends strongly on the type of error. We further analyze asymmetric errors between the two parties and identify conditions under which complementary postselection outcomes yield identical distillation dynamics, allowing the success probability to be enhanced.

quant-pharXiv:2610.35699•Oct 27, 2026•0 citations

Near-optimal entanglement-communication tradeoffs for remote state preparation

Srijita Kundu, Olivier Lalonde

We study the following task: Alice is given a classical description of a rank-$k$ projector $P$ on $\mathbb{C}^d$, and Alice and Bob want to prepare the quantum state $P/k$ on Bob's side using shared entanglement and classical communication. The general form of this task is known as remote state preparation (RSP). We give nearly-matching lower and upper bounds for the entanglement cost and communication cost for RSP of the states $P/k$. Ours are the first nearly matching upper and lower bounds for RSP of mixed states, and in the special case of pure states, our lower bound outperforms the best previously known lower bound. Our results show that any pure entangled state that can be used to do RSP of these states with $o(d)$ bits of communication, can distill $\log d$ ebits of entanglement, and conversely, any state that can distill $\log d$ ebits of entanglement can be used to do RSP of these states efficiently. As applications of our results, we rederive a previously-known incompressibility result for states of the form $P/k$, and give a new entanglement-assisted communication protocol for the equality function that uses $\frac{1}{2}\log n + O(1)$ many ebits, and $O(1)$ communication.

quant-pharXiv:2602.09428•Feb 11, 2026•0 citations
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].
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 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].
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.
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.
We recently proposed an entanglement distillation protocol based on local operations and classical communication that probabilistically and universally distills a maximally entangled Bell pair from multiple copies of an unknown two-qubit state [Phys. Rev. Lett. 135, 260202 (2025)]. Here, we investigate the robustness of this protocol against imperfections in its implementation. We consider several incoherent and coherent gate-error models, as well as measurement readout errors, and determine the regimes in which distillation enhances the fidelity with the target Bell state. We find that the protocol remains effective over substantial error ranges, although its robustness depends strongly on the type of error. We further analyze asymmetric errors between the two parties and identify conditions under which complementary postselection outcomes yield identical distillation dynamics, allowing the success probability to be enhanced.
We study the following task: Alice is given a classical description of a rank-kkk projector PPP on Cd\mathbb{C}^dCd, and Alice and Bob want to prepare the quantum state P/kP/kP/k on Bob's side using shared entanglement and classical communication. The general form of this task is known as remote state preparation (RSP). We give nearly-matching lower and upper bounds for the entanglement cost and communication cost for RSP of the states P/kP/kP/k. Ours are the first nearly matching upper and lower bounds for RSP of mixed states, and in the special case of pure states, our lower bound outperforms the best previously known lower bound. Our results show that any pure entangled state that can be used to do RSP of these states with o(d)o(d)o(d) bits of communication, can distill log⁡d\log dlogd ebits of entanglement, and conversely, any state that can distill log⁡d\log dlogd ebits of entanglement can be used to do RSP of these states efficiently. As applications of our results, we rederive a previously-known incompressibility result for states of the form P/kP/kP/k, and give a new entanglement-assisted communication protocol for the equality function that uses 12log⁡n+O(1)\frac{1}{2}\log n + O(1)21​logn+O(1) many ebits, and O(1)O(1)O(1) communication.