Preparing Many Copies of a Quantum State in the Black-Box Model

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(√N). In comparison with the naive O(K√N) solution obtained by repeating this procedure~K times, our algorithm achieves the optimal running time of θ(√KN). Our technique uses a refinement of the quantum rejection sampling method employed by Grover. As a direct application, we obtain a similar speed-up for obtaining K independent samples from a distribution whose probability vector is given by a quantum oracle.