  We study a variant of quantum circuit complexity, the binding complexity:
Consider a $n$-qubit system divided into two sets of $k_1$, $k_2$ qubits each
($k_1\leq k_2$) and gates within each set are free; what is the least cost of
two-qubit gates ''straddling'' the sets for preparing an arbitrary quantum
state, assuming no ancilla qubits allowed? Firstly, our work suggests that,
without making assumptions on the entanglement spectrum, $\Theta(2^{k_1})$
straddling gates always suffice. We then prove any $\text{U}(2^n)$ unitary
synthesis can be accomplished with $\Theta(4^{k_1})$ straddling gates.
Furthermore, we extend our results to multipartite systems, and show that any
$m$-partite Schmidt decomposable state has binding complexity linear in $m$,
which hints its multi-separable property. This result not only resolves an open
problem posed by Vijay Balasubramanian, who was initially motivated by the
''Complexity=Volume'' conjecture in quantum gravity, but also offers realistic
applications in distributed quantum computation in the near future.
