Quantum Simulators, Continuous-Time Automata, and Translationally Invariant Systems

The general problem of finding the ground state energy of lattice Hamiltonians is known to be very hard, even for a quantum computer. We show here that this is the case even for translationally invariant systems in 1D. We also show that a quantum computer can be built in a 1D chain with a fixed, translationally invariant Hamitonian consisting of nearest-neighbor interactions only. The result of the computation is obtained after a prescribed time with high probability.

Figure 1

(a) A 7-qubit quantum computer encoded into a 1D chain. The pointer is represented by the 1, the program is encoded to the left of the quantum computer. The sites are counted from the left to the right. (b) The system can be mapped onto another system, where every command correspond to an electron that is allowed to hop to nearby sites.