Paper Info
Title
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information
Abstract
Entanglement is an essential resource for quantum communicationand quantum computation, similar to sharedrandom bits in the classical world. Entanglement distillationextracts nearly-perfect entanglement from imperfectentangled state. The classical communication complexity ofthese protocols is the minimal amount of classical informationthat needs to be exchanged for the conversion. In thispaper, we focus on the communication complexity of protocolsthat 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 depolarizationmodel, and the fidelity model. We describe there modelsas well as the motivations for studying them. For thebounded measurement model and the depolarization model,we prove tight and almost-tight bounds on the output qualityof non-interactive protocols. For the fidelity model weprove a lower bound that matches the upper bound given byAmbainis et al., and thus completely characterizes communicationcomplexity of entanglement distillation protocolsfor 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, twonovel techniques are developed for proving these results.We believe that these techniques are of independent interests,too.
Year
DOI
Venue
2003
10.1109/CCC.2004.39
CCC '04 Proceedings of the 19th IEEE Annual Conference on Computational Complexity
Keywords
DocType
ISSN
entanglement distillation protocolsfor,fidelity model,imperfect entanglement,nearly-perfect entanglement,thebounded measurement model,entanglement distillationextracts,incomplete information,bounded measurement model,classical communication complexity,fidelity model weprove,entanglement distillation protocols,depolarization model,communication complexity,lower bound,protocols,teleportation,quantum computing,quantum mechanics,information theory,upper bound,quantum entanglement,quantum computation,quantum communication,data mining,quantum computer,quantum physics
Journal
1093-0159
ISBN
Citations 
PageRank 
0-7695-2120-7
0
0.34
References 
Authors
22
2
Name
Order
Citations
PageRank
Andris Ambainis12000183.24
Ke Yang241131.93