  We show that the depth of quantum circuits in the realistic architecture
where a classical controller determines which local interactions to apply on
the kD grid Z^k where k >= 2 is the same (up to a constant factor) as in the
standard model where arbitrary interactions are allowed. This allows
minimum-depth circuits (up to a constant factor) for the nearest-neighbor
architecture to be obtained from minimum-depth circuits in the standard
abstract model. Our work therefore justifies the standard assumption that
interactions can be performed between arbitrary pairs of qubits. In particular,
our results imply that Shor's algorithm, controlled operations and fanouts can
be implemented in constant depth, polynomial size and polynomial width in this
architecture.
  We also present optimal non-adaptive quantum circuits for controlled
operations and fanouts on a kD grid. These circuits have depth Theta(n^(1 /
k)), size Theta(n) and width Theta(n). Our lower bound also applies to a more
general class of operations.
