Preparing many copies of a quantum state in the black-box model

Overview & Synopsis

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.