Universal Adiabatic Quantum Computation via the Space-Time Circuit-to-Hamiltonian Construction

We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic $XXZ$ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its $q$-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young’s lattice.

Figure 1

A quantum circuit of the form shown in (a) (each gray square is a two qubit gate) is mapped to a Hamiltonian which describes a system of interacting particles that live on the edges of the rotated grid shown in (b). In the ground state, the edges occupied by particles form a connected string, as illustrated by the thick (red) line. (c) Many of the gates are fixed to be the identity; the gates which are unrestricted correspond to plaquettes within a $k\times k$ subgrid, the “interaction region,” with the left corner in the center of the grid (shown in black).

Figure 2

Young’s lattice.