title: Classical simulation of limited-width cluster-state quantum computation.
abstract: We present a classical protocol, using the matrix product-state representation, to simulate cluster-state quantum computation at a cost polynomial in the number of qubits in the cluster and exponential in d---the width of the cluster. We use this result to show that any log-depth quantum computation in the gate array model, with gates linking only nearby qubits, can be simulated efficiently on a classical computer.
authors.affiliation: HH Wills Physics Laboratory, University of Bristol, UK. N.Yoran@bristol.ac.uk
authors.forename: Nadav
authors.initials: N
authors.lastname: Yoran
authors.forename: Anthony J
authors.initials: AJ
authors.lastname: Short