  We extend the idea of a discrete-time quantum walk on a graph by placing a
qubit on each vertex, and allowing the walker to interact with the qubit at its
current position. We show that allowing for a controlled-Z interaction at each
time step between the walker and the vertex qubits generates multipartite
entanglement between the qubits. We demonstrate that for particular coin
operators the system generates a highly entangled cluster state, of use in
measurement based quantum computation.
