Quantum computation in the ground state of interacting fermions

In measurement-based quantum computation (MBQC), an algorithm proceeds entirely by making projective measurements on successive qubits comprising some highly entangled `resource state.' While two-dimensional cluster states are known to be universal resources for MBQC, it has been proven that they cannot be the unique ground states of any two-body spin Hamiltonian. We show that a particular ground state of non-interacting fermions (equivalent to a many-body spin system) is formally equivalent to a cluster state, though only capable of simulating a limited set of quantum operations. In the presence of two-particle interactions, however, the ground state becomes a universal resource for MBQC. This result suggests that arbitrary quantum algorithms could be simulated fault-tolerantly simply by measuring a cold gas of interacting fermions, such as ultracold atoms in optical lattices.