Reducing the communication complexity with quantum entanglement

Peng Xue, Yun-Feng Huang, Yong-Sheng Zhang, Chuan-Feng Li, Guang-Can Guo

Published 2000-12-13Version 1

We propose a probabilistic two-party communication complexity scenario with a prior nonmaximally entangled state, which results in less communication than that is required with only classical random correlations. A simple all-optical implementation of this protocol is presented and demonstrates our conclusion.