  As a cornerstone for many quantum linear algebraic and quantum machine
learning algorithms, controlled quantum state preparation (CQSP) aims to
provide the transformation of $|i\rangle |0^n\rangle \to |i\rangle
|\psi_i\rangle $ for all $i\in \{0,1\}^k$ for the given $n$-qubit states
$|\psi_i\rangle$. In this paper, we construct a quantum circuit for
implementing CQSP, with depth $O\left(n+k+\frac{2^{n+k}}{n+k+m}\right)$ and
size $O\left(2^{n+k}\right)$ for any given number $m$ of ancillary qubits.
These bounds, which can also be viewed as a time-space tradeoff for the
transformation, are \optimal for any integer parameters $m,k\ge 0$ and $n\ge
1$. When $k=0$, the problem becomes the canonical quantum state preparation
(QSP) problem with ancillary qubits, which asks for efficient implementations
of the transformation $|0^n\rangle|0^m\rangle \to |\psi\rangle |0^m\rangle$.
This problem has many applications with many investigations, yet its circuit
complexity remains open. Our construction completely solves this problem,
pinning down its depth complexity to $\Theta(n+2^{n}/(n+m))$ and its size
complexity to $\Theta(2^{n})$ for any $m$. Another fundamental problem, unitary
synthesis, asks to implement a general $n$-qubit unitary by a quantum circuit.
Previous work shows a lower bound of $\Omega(n+4^n/(n+m))$ and an upper bound
of $O(n2^n)$ for $m=\Omega(2^n/n)$ ancillary qubits. In this paper, we
quadratically shrink this gap by presenting a quantum circuit of the depth of
$O\left(n2^{n/2}+\frac{n^{1/2}2^{3n/2}}{m^{1/2}}\right)$.
