  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.
