  We prove that magic states from the Clifford hierarchy give optimal solutions
for tasks involving nonlocality and entropic uncertainty with respect to Pauli
measurements. For both the nonlocality and uncertainty tasks, stabilizer states
are the worst possible pure states so our solutions have an operational
interpretation as being highly non-stabilizer. The optimal strategy for a qudit
version of the Clauser-Horne-Shimony-Holt (CHSH) game in prime dimensions is
achieved by measuring maximally entangled states that are isomorphic to
single-qudit magic states. These magic states have an appealingly simple form
and our proof shows that they are "balanced" with respect to all but one of the
mutually unbiased stabilizer bases. Of all equatorial qudit states, magic
states minimize the average entropic uncertainties for collision entropy and
also, for small prime dimensions, min-entropy -- a fact that may have
implications for cryptography.
