# Quantum Communication Complexity (A Survey)

**Authors:** Gilles Brassard  
**arXiv:** [quant-ph/0101005](https://arxiv.org/abs/quant-ph/0101005)  
**Date:** 2001-01-01  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/quant-ph--0101005v1/

## Key points

- Quantum communication is explored as more efficient than classical communication in the survey paper "Quantum Communication Complexity" by Gilles Brassard.
- Holevo's theorem sets a limit on the amount of classical information that can be transmitted through quantum bits, stating that no more than n bits of classical information can be conveyed using n quantum bits unless parties are entangled.
- Entanglement allows for twice as many classical bits to be communicated in cases where it is present, but no more.
- The paper discusses contradictions in distributed computational tasks and scenarios where quantum communication cannot be efficiently simulated using classical methods.
- Achieving the effects of transmitting quantum bits classically would require an exponentially larger number of bits in extreme cases.
- Entanglement has the potential to reduce the need for classical communication, making certain distributed tasks feasible if non-communicating parties share prior entanglement.
- The unique capabilities of entanglement raise questions about accurately simulating them in terms of classical communication.

## Summary

In the survey paper "Quantum Communication Complexity," authored by Gilles Brassard, the concept of quantum communication being more efficient than its classical counterpart is explored. The paper discusses Holevo's theorem, which sets a limit on the amount of classical information that can be transmitted through quantum bits. This theorem states that no more than n bits of classical information can be conveyed using n quantum bits unless the parties involved are entangled. In cases where entanglement is present, twice as many classical bits can be communicated, but no more. The paper also delves into apparent contradictions in distributed computational tasks and highlights scenarios where quantum communication cannot be efficiently simulated using classical methods. It points out that in extreme cases, achieving the effects of transmitting quantum bits classically would require an exponentially larger number of bits. Additionally, the discussion extends to the potential for entanglement to reduce the need for classical communication. While entanglement alone is ineffective for transmitting information, there are instances where distributed tasks that are impossible in a purely classical setting become feasible if non-communicating parties share prior entanglement. This raises questions about the cost of accurately simulating the unique capabilities of entanglement in terms of classical communication. Overall, "Quantum Communication Complexity" provides insights into the intricate relationship between quantum and classical communication methods and sheds light on how entanglement can play a crucial role in certain computational tasks that transcend traditional communication boundaries.