Fast universal quantum computation with railroad-switch local Hamiltonians

We present two universal models of quantum computation with a time-independent, frustration-free Hamiltonian. The first construction uses 3-local (qubit) projectors and the second one requires only 2-local qubit-qutrit projectors. We build on Feynman's Hamiltonian computer idea [R. Feynman, Optics News 11, 11 (1985)] and use a railroad-switch-type clock register. The resources required to simulate a quantum circuit with L gates in this model are O(L) small-dimensional quantum systems (qubits or qutrits), a time-independent Hamiltonian composed of O(L) local, constant norm, projector terms, the possibility to prepare computational basis product states, a running time O(L log(2) L), and the possibility to measure a few qubits in the computational basis. Our models also give a simplified proof of the universality of 3-local adiabatic quantum computation. (C) 2010 American Institute of Physics. [doi:10.1063/1.3384661]