  A crucial subroutine in quantum computing is to load the classical data of
$N$ complex numbers into the amplitude of a superposed $n=\lceil
\log_2N\rceil$-qubit state. It has been proven that any algorithm universally
implementing this subroutine would need at least $\mathcal O(N)$ constant
weight operations. However, the proof assumes that only $n$ qubits are used,
whereas the circuit depth could be reduced by extending the space and allowing
ancillary qubits. Here we investigate this space-time tradeoff in quantum state
preparation with classical data. We propose quantum algorithms with $\mathcal
O(n^2)$ circuit depth to encode any $N$ complex numbers using only single-,
two-qubit gates and local measurements with ancillary qubits. Different
variances of the algorithm are proposed with different space and runtime. In
particular, we present a scheme with $\mathcal O(N^2)$ ancillary qubits,
$\mathcal O(n^2)$ circuit depth, and $\mathcal O(n^2)$ average runtime, which
exponentially improves the conventional bound. While the algorithm requires
more ancillary qubits, it consists of quantum circuit blocks that only
simultaneously act on a constant number of qubits and at most $\mathcal O(n)$
qubits are entangled. We also prove a fundamental lower bound $\mit\Omega(n)$
for the minimum circuit depth and runtime with arbitrary number of ancillary
qubits, aligning with our scheme with $\mathcal O(n^2)$. The algorithms are
expected to have wide applications in both near-term and universal quantum
computing.
