Random exclusion codes as vector random walks

Abstract

Random exclusion codes (RECs) are one-shot communication tasks in which Alice receives a uniformly random word and sends a limited physical system to Bob, who is asked to output a symbol different from the one appearing at a randomly selected coordinate. We resolve the conjectured quantum advantage in the comparison between one communicated classical bit and one communicated qubit for arbitrary word length and alphabet size.