We present and experimentally demonstrate a communication protocol that employs shared entanglement to reduce errors when sending a bit over a particular noisy classical channel. Specifically, it is shown that, given a single use of this channel, one
can transmit a bit with higher success probability when sender and receiver share entanglement compared to the best possible strategy when they do not. The experiment is realized using polarization-entangled photon pairs, whose quantum correlations play a critical role in both the encoding and decoding of the classical message. Experimentally, we find that a bit can be successfully transmitted with probability 0.891 pm 0.002, which is close to the theoretical maximum of (2 + 2^-1/2)/3 simeq 0.902 and is significantly above the optimal classical strategy, which yields 5/6 simeq 0.833.
