Hamiltonian quantum computer in one dimension

Quantum computation can be achieved by preparing an appropriate initial product state of qudits and then letting it evolve under a fixed Hamiltonian. The readout is made by measurement on individual qudits at some later time. This approach is called the Hamiltonian quantum computation and it includes, for example, the continuous-time quantum cellular automata and the universal quantum walk. We consider one spatial dimension and study the compromise between the locality k and the local Hilbert space dimension d. For geometrically 2-local (i.e.; k=2), it is known that d=8 is already sufficient for universal quantum computation but the Hamiltonian is not translationally invariant. As the locality k increases, it is expected that the minimum required d should decrease. We provide a construction of a Hamiltonian quantum computer for k=3 with d=5. One implication is that simulating one-dimensional chains of spin-2 particles is BQP-complete (BQP denotes "bounded error, quantum polynomial time"). Imposing translation invariance will increase the required d. For this we also construct another 3-local (k=3) Hamiltonian that is invariant under translation of a unit cell of two sites but that requires d to be 8.