  A single physical interaction might not be universal for quantum computation
in general. It has been shown, however, that in some cases it can generate
universal quantum computation over a subspace. For example, by encoding logical
qubits into arrays of multiple physical qubits, a single isotropic or
anisotropic exchange interaction can generate a universal logical gate-set.
Recently, encoded universality for the exchange interaction was explicitly
demonstrated on three-qubit arrays, the smallest nontrivial encoding. We now
present the exact specification of a discrete universal logical gate-set on
four-qubit arrays. We show how to implement the single qubit operations exactly
with at most 3 nearest neighbor exchange operations and how to generate the
encoded controlled-not with 29 parallel nearest neighbor exchange interactions
or 54 serial gates, obtained from extensive numerical optimization using
genetic algorithms and Nelder-Mead searches. Our gate-sequences are immediately
applicable to implementations of quantum circuits with the exchange
interaction.
