= Solution
The essential requirement is an efficient <quantum state preparation> circuit $B$ satisfying
$$
B|0^n\rangle=|b\rangle
=\frac1{\|b\|}\sum_{j=0}^{N-1}b_j|j\rangle.
$$
A standard sufficient promise is that $b$ has only $\operatorname{poly}(\log N)$ nonzero components, with their positions and values classically computable to the required precision in $\operatorname{poly}(\log N)$ time, and with efficiently computable normalization. More structured dense vectors are also allowed whenever cumulative weights or an equivalent data-access oracle permit amplitude encoding in polylogarithmic time. Without such a promise, merely loading $N$ arbitrary classical entries already costs $\Omega(N)$ and removes the claimed exponential dependence on dimension.
Back to article page
