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\left(\sqrt{N}\right)$. In comparison with the naive $O\left(K\sqrt{N}\right)$ solution obtained by repeating this procedure $K$ times, our algorithm achieves the optimal running time of $\mathrm{\Theta }\left(\sqrt{KN}\right)$. 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.

Figure 1

Three gates used in our circuits. The state $|\chi \rangle$ is defined as $\sqrt{\frac{v}{h}}|b\rangle +\sqrt{1-\frac{v}{h}}|1-b\rangle$ if $0<v\le h$, and $|b\rangle$ otherwise.

Figure 2

Circuit $\mathcal{C}$ output at the end of the preprocessing phase (Algorithm 1).