Abstract:

That quantum walks can be made universal for quantum computation has been known for over twenty years.  Previous constructions required Hamiltonians to act on ever-distantly separated systems as the computation size grew.  In this talk, I describe how to achieve quantum walk universality using a Hamiltonian that acts on nearest-neighbor spins in one dimension.  This opens up the possibility of a new kind of "control-free" quantum computing architecture.  To run an algorithm in this architecture, one prepares the initial state of the spin system so that it describes the program of interest and the data on which it is to act, waits for the quantum walk to apply the program to the data, and then measures the data to get an answer.  A corollary of this quantum walk construction is that there is no efficient classical algorithm for simulating generic spin chain dynamics in one dimension if the state space of each spin is eight or greater.

Based on joint work with Brad Chase in arXiv:0802.1207.

(PLEASE NOTE NON-STANDARD DATE )