  The surface code is a leading candidate quantum error correcting code, owing
to its high threshold, and compatibility with existing experimental
architectures. Bravyi et al. (2006) showed that encoding a state in the surface
code using local unitary operations requires time at least linear in the
lattice size $L$, however the most efficient known method for encoding an
unknown state, introduced by Dennis et al. (2002), has $O(L^2)$ time
complexity. Here, we present an optimal local unitary encoding circuit for the
planar surface code that uses exactly $2L$ time steps to encode an unknown
state in a distance $L$ planar code. We further show how an $O(L)$ complexity
local unitary encoder for the toric code can be found by enforcing locality in
the $O(\log L)$-depth non-local renormalisation encoder. We relate these
techniques by providing an $O(L)$ local unitary circuit to convert between a
toric code and a planar code, and also provide optimal encoders for the
rectangular, rotated and 3D surface codes. Furthermore, we show how our
encoding circuit for the planar code can be used to prepare fermionic states in
the compact mapping, a recently introduced fermion to qubit mapping that has a
stabiliser structure similar to that of the surface code and is particularly
efficient for simulating the Fermi-Hubbard model.
