Preparing many copies of a quantum state in the black-box model
Yassine Hamoudi · Physical Review A · 2022
We describe a simple quantum algorithm for preparing $K$ copies of an $N$-dimensional quantum state whose amplitudes are given by a quantum oracle. Our result extends a previous work of Grover, who showed how to prepare one copy in time $O(\sqrt{N})$. In comparison with the naive $O(K\sqrt{N})$ solution obtained by repeating this procedure $K$ times, our algorithm achieves the optimal running time of $\mathrm{\ensuremath{\Theta}}(\sqrt{KN})$. Our technique uses a refinement of the quantum rejection sampling method employed by Grover. As a direct application, we obtain a similar speedup for obtaining $K$ independent samples from a distribution whose probability vector is given by a quantum oracle.