Strict advantage of complex quantum theory in a communication task

Standard formulations of quantum theory are based on complex numbers: Quantum states can be in superpositions, with weights given by complex probability amplitudes. Motivated by quantum theory promising a range of practical advantages over classical for a multitude of tasks, we investigate how the presence of complex amplitudes in quantum theory can yield operational advantages over counterpart real formulations. We identify a straightforward communication task for which complex quantum theory exhibits a provably lower communication cost than not just any classical approach, but also any approach based on real quantum theory. We certify the necessity of complex quantum theory for optimal approaches to the task through geometric properties of quantum state ensembles that witness the presence of basis-independent complexity. This substantiates a strict operational advantage of complex quantum theory. We discuss the relevance of this finding for quantum advantages in stochastic simulation.