  The treewidth of a graph is a useful combinatorial measure of how close the
graph is to a tree. We prove that a quantum circuit with $T$ gates whose
underlying graph has treewidth $d$ can be simulated deterministically in
$T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in $T$ if
$d=O(\log T)$. Among many implications, we show efficient simulations for
log-depth circuits whose gates apply to nearby qubits only, a natural
constraint satisfied by most physical implementations. We also show that
one-way quantum computation of Raussendorf and Briegel (Physical Review
Letters, 86:5188--5191, 2001), a universal quantum computation scheme with
promising physical implementations, can be efficiently simulated by a
randomized algorithm if its quantum resource is derived from a small-treewidth
graph.

Quantum Physics