A Caltech Library Service

On communication over an entanglement-assisted quantum channel

Nayak, Ashwin and Salzman, Julia (2002) On communication over an entanglement-assisted quantum channel. In: STOC '02 Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM Press , New York, pp. 698-704. ISBN 1-58113-495-9.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols. Whereas shared randomness does not help in the transmission of information, or significantly reduce the classical complexity of computing functions (as compared to private-coin protocols), shared entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding."The problem of characterising the power of prior entanglement has puzzled many researchers. In this paper, we revisit the problem of transmitting classical bits over an entanglement-assisted quantum channel. We derive a new, optimal bound on the number of quantum bits required for this task, for any given probability of error. All known lower bounds in the setting of bounded error entanglement-assisted communication are based on sophisticated information theoretic arguments. In contrast, our result is derived from first principles, using a simple linear algebraic technique.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Nayak, Ashwin0000-0002-3924-0875
Additional Information:© 2002 ACM, Inc. Supported by Charles Lee Powell Foundation, and NSF grants CCR 0049092 and EIA 0086038. A part of this work was done while this author was visiting Caltech on a Summer Undergraduate Research Fellowship. We would like to thank Leonard Schulman for insightful discussions, and Umesh Vazirani and the anonymous referees for helpful comments on the paper.
Funding AgencyGrant Number
Charles Lee Powell FoundationUNSPECIFIED
NSFCCR 0049092
Subject Keywords:Quantum communication, entanglement-assisted quantum channel, communication complexity
Record Number:CaltechAUTHORS:20111109-143752204
Persistent URL:
Official Citation:On communication over an entanglement-assisted quantum channel Ashwin Nayak, Julia Salzman Pages: 698 - 704 doi>10.1145/509907.510007
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27715
Deposited By: Ruth Sustaita
Deposited On:09 Nov 2011 23:50
Last Modified:09 Nov 2021 16:51

Repository Staff Only: item control page