论文标题
在黑框模型中准备许多量子状态的副本
Preparing Many Copies of a Quantum State in the Black-Box Model
论文作者
论文摘要
我们描述了一种简单的量子算法，用于准备$ n $二维量子状态的$ k $副本，其幅度由量子甲骨文提供。我们的结果扩展了格罗弗先前的工作，他们展示了如何在时间上准备一个副本$ o（\ sqrt {n}）$。与通过重复此过程〜$ k $ times获得的幼稚$ o（k \ sqrt {n}）$解决方案相比，我们的算法达到了$θ（\ sqrt {kn}）$的最佳运行时间。我们的技术使用了Grover采用的量子排斥采样方法的改进。作为直接应用程序，我们获得了类似的速度，用于从量子甲骨文给出概率向量的分布中获取$ k $独立的样本。
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 $θ(\sqrt{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.
