  We investigate graphs that can be disconnected into small components by
removing a vanishingly small fraction of their vertices. We show that when a
quantum network is described by such a graph, the network is efficiently
controllable, in the sense that universal quantum computation can be performed
using a control sequence polynomial in the size of the network while
controlling a vanishingly small fraction of subsystems. We show that networks
corresponding to finite-dimensional lattices are efficently controllable, and
explore generalizations to percolation clusters and random graphs. We show that
the classical computational complexity of estimating the ground state of
Hamiltonians described by controllable graphs is polynomial in the number of
subsystems/qubits.
