  Some physical implementation schemes of quantum computing can apply two-qubit
gates only on certain pairs of qubits. These connectivity constraints are
commonly viewed as a significant disadvantage. For example, compiling an
unrestricted $n$-qubit quantum circuit to one with poor qubit connectivity,
such as a 1D chain, usually results in a blowup of depth by $O(n^2)$ and size
by $O(n)$. It is appealing to conjecture that this overhead is unavoidable -- a
random circuit on $n$ qubits has $\Theta(n)$ two-qubit gates in each layer and
a constant fraction of them act on qubits separated by distance $\Theta(n)$.
  While it is known that almost all $n$-qubit unitary operations need quantum
circuits of $\Omega(4^n/n)$ depth and $\Omega(4^n)$ size to realize with
all-to-all qubit connectivity, in this paper, we show that all $n$-qubit
unitary operations can be implemented by quantum circuits of $O(4^n/n)$ depth
and $O(4^n)$ size even under {1D chain} qubit connectivity constraint.
  We extend this result and investigate qubit connectivity in three directions.
First, we consider more general connectivity graphs and show that the circuit
size can always be made $O(4^n)$ as long as the graph is connected. For circuit
depth, we study $d$-dimensional grids, complete $d$-ary trees and expander
graphs, and show results similar to the 1D chain. Second, we consider the case
when ancillary qubits are available. We show that, with ancilla, the circuit
depth can be made polynomial, and the space-depth trade-off is not impaired by
connectivity constraints unless we have exponentially many ancillary qubits.
Third, we obtain nearly optimal results on special families of unitaries,
including diagonal unitaries, 2-by-2 block diagonal unitaries, and Quantum
State Preparation (QSP) unitaries, the last being a fundamental task used in
many quantum algorithms for machine learning and linear algebra.
