  In some physical implementations of quantum computers, 2-qubit operations can
be applied only on certain pairs of qubits. Compilation of a quantum circuit
into one compliant to such qubit connectivity constraint results in an increase
of circuit depth. Various compilation algorithms were studied, yet what this
depth overhead is remains elusive. In this paper, we fully characterize the
depth overhead by the routing number of the underlying constraint graph, a
graph-theoretic measure which has been studied for 3 decades. We also give
reduction algorithms between different graphs, which allow compilation for one
graph to be transferred to one for another. These results, when combined with
existing routing algorithms, give asymptotically optimal compilation for all
commonly seen connectivity graphs in quantum computing.
