= Solution
Apply <Hadamard gates> to $|0^m\rangle$ to prepare
$$
2^{-m/2}\sum_{x=0}^{2^m-1}|x\rangle.
$$
Reversibly compute the efficiently decidable predicate $[x<Q]$ into an ancillary qubit and measure it. The success probability is $Q/2^m>1/2$, and conditioned on success the first register is exactly
$$
|\xi\rangle=\frac1{\sqrt Q}\sum_{b=0}^{Q-1}|b\rangle.
$$
Restart after a failed measurement. After $L=\lceil\log_2(1/\delta)\rceil$ attempts, the probability that all attempts fail is below $\delta$, so the state is prepared with probability at least $1-\delta$ using a number of gates polynomial in $m$ and $\log(1/\delta)$.
Back to article page
