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

On communication over an entanglement-assisted quantum channel

Ashwin Nayak, Julia Salzman

Published Jun 19, 2002• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.quant-ph/0206122

Related papers

On communication over an entanglement-assisted quantum channel

Ashwin Nayak, Julia Salzman

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.

ACM Symposium on Theory of Computing (STOC)•May 19, 2002•27 citations

On communication over an entanglement-assisted quantum channel

Ashwin Nayak, Julia Salzman

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.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 2002•1 citation

On communication over an entanglement-assisted quantum channel. (arXiv:quant-ph/0206122v1 CROSS LISTED)

Ashwin Nayak, Julia Salzman

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.

•Mar 21, 2018•0 citations

On communication over an entanglement-assisted quantum channel

A. Nayak, Julia Salzman

Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.

IEEE Conference on Computational Complexity (CCC)•Jun 25, 2003•10 citations

Limits on the ability of quantum states to convey classical messages

Ashwin Nayak, Julia Salzman

We revisit the problem of conveying classical messages by transmitting quantum states, and derive new, optimal bounds on the number of quantum bits required for this task. Much of the previous work on this problem, and on other communication tasks in the setting of bounded error entanglement-assisted communication, is based on sophisticated information theoretic arguments. Our results are derived from first principles, using a simple linear algebraic technique. A direct consequence is a tight lower bound for the Inner Product function that has found applications to privacy amplification in quantum key distribution protocols.

Journal of the ACM•Jan 1, 2006•36 citations

Codes for entanglement-assisted classical communication

Tushita Prasad, Markus Grassl

Abstract Entanglement-assisted classical communication (EACC) aims to enhance communication systems using entanglement as an additional resource. However, there is a scarcity of explicit protocols designed for finite transmission scenarios, which presents a challenge for real-world implementation. In response, we introduce a new EACC scheme capable of correcting a fixed number of erasures/errors. It can be adjusted to the available amount of entanglement and sends classical information over a quantum channel. We establish a general framework to accomplish such a task by reducing it to a classical problem. Comparing with specific bounds, we identify optimal parameter ranges. The scheme requires only the implementation of super-dense coding which has been demonstrated successfully in experiments. Furthermore, our results show that an adaptable entanglement use confers a communication advantage. Overall, our work sheds light on how entanglement can elevate various finite-length communication protocols, opening new avenues for exploration in the field.

arXiv:2310.19774•npj Quantum Information•Jan 27, 2025•3 citations
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.
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.
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.
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.
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.
We revisit the problem of conveying classical messages by transmitting quantum states, and derive new, optimal bounds on the number of quantum bits required for this task. Much of the previous work on this problem, and on other communication tasks in the setting of bounded error entanglement-assisted communication, is based on sophisticated information theoretic arguments. Our results are derived from first principles, using a simple linear algebraic technique. A direct consequence is a tight lower bound for the Inner Product function that has found applications to privacy amplification in quantum key distribution protocols.
Abstract Entanglement-assisted classical communication (EACC) aims to enhance communication systems using entanglement as an additional resource. However, there is a scarcity of explicit protocols designed for finite transmission scenarios, which presents a challenge for real-world implementation. In response, we introduce a new EACC scheme capable of correcting a fixed number of erasures/errors. It can be adjusted to the available amount of entanglement and sends classical information over a quantum channel. We establish a general framework to accomplish such a task by reducing it to a classical problem. Comparing with specific bounds, we identify optimal parameter ranges. The scheme requires only the implementation of super-dense coding which has been demonstrated successfully in experiments. Furthermore, our results show that an adaptable entanglement use confers a communication advantage. Overall, our work sheds light on how entanglement can elevate various finite-length communication protocols, opening new avenues for exploration in the field.