Hamiltonian quantum cellular automata in one dimension

We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of ten-dimensional qudits that makes it possible to realize universal quantum computing without any external control during the computational process. We only require the ability to prepare an initial computational basis state that encodes both the quantum circuit and its input. The computational process is then carried out by the autonomous Hamiltonian time evolution. After a time polynomially long in the size of the quantum circuit has passed, the result of the computation is obtained with high probability by measuring a few qudits in the computational basis. This result also implies that there cannot exist efficient classical simulation methods for generic translationally invariant nearest-neighbor Hamiltonians on qudit chains, unless quantum computers can be efficiently simulated by classical computers (or, put in complexity theoretic terms, unless $\mathrm{BPP}=\mathrm{BQP}$).

Figure 1

(a) A quantum circuit consisting of two rounds of gates acting on nearest neighbors. (b) The previous circuit with a third round of identity gates added.

Figure 2

The initial state $\mid \phi ⟩$ of the qudit chain for the circuit in Fig. 1a.

Figure 3

(Color online) Analysis of the second rule (8). (a) A gate meeting a pointer above two extra qubits in the state ∣00⟩. (b) The gate meeting a pointer above the right boundary of the work qubits is the identity gate. (c) The only gate meeting a pointer above the left boundary of the work qubits is the identity gate.