Rigidity is a phenomenon in which optimal performance in an information

processing task constrains a protocol into assuming a highly structured form. In some cases, there is essentially a *unique* optimal protocol. A prototypical example is that of the CHSH experiment in which any quantum strategy achieving the optimal violation of the eponymous inequality is identical to a canonical protocol, up to local changes of basis. This phenomenon has been at the heart of a number of applications, such as the generation of certified random bits and classical verification of quantum computation.



We investigate the rigidity properties of the famous superdense coding protocol due to Bennett and Wiesner, which demonstrates that it is possible to communicate two bits of classical information by sending only one qubit and using a shared Bell state. We show that the superdense coding task is *rigid*, in that any protocol for the task that uses only one qubit of communication is *locally equivalent* to the Bennett-Wiesner protocol.



We also study higher-dimensional superdense coding, where the goal is to communicate one of d^2 possible classical messages by sending a d-dimensional quantum state, for general dimensions d. Unlike the d=2 case, there are non-equivalent superdense coding protocols for higher d. We present concrete constructions of non-equivalent protocols for all d > 2. Finally, we analyze the performance of superdense coding protocols where the encoding operators are independently sampled from the Haar measure on the unitary group. The analysis involves bounding the distinguishability of random maximally entangled states, which

may be of independent interest.



This is joint work with Henry Yuen.