  An open problem of quantum information theory has been to determine under
what conditions universal exchange-only computation is possible for qudits
encoded on $d$-state systems for $d>2$. This problem can be posed in terms of
representation theory by recognizing that each quantum mechanical swap,
generated by exchange-interaction, can be identified with a transposition in a
symmetric group, each $d$-state system can be identified with the fundamental
representation of $SU(d)$, and each encoded qudit can be identified with an
irreducible representation of a Lie algebra generated by transpositions.
Towards this end we first give a mathematical definition of exchange-only
universality in terms of a map from the special unitary algebra on the product
of qudits into a representation of a Lie algebra generated by transpositions.
We show that this definition is consistent with quantum computing requirements.
We then proceed with the task of characterizing universal families of qudits,
that is families of encoded qudits admitting exchange-only universality. This
endeavor is aided by the fact that the irreducible representations
corresponding to qudits are canonically labeled by partitions. In particular we
derive necessary and sufficient conditions for universality on one or two such
qudits, in terms of simple arithmetic conditions on the associated partitions.
We also derive necessary and sufficient conditions for universality on
arbitrarily many such qudits, in terms of Littlewood--Richardson coefficients.
Among other results, we prove that universal families of multiple qudits are
upward closed, that universality is guaranteed for sufficiently many qudits,
and that any family that is not universal can be made so by simply adding at
most five ancillae. We also obtain results for 2-state systems as a special
case.
