论文标题
快速黑盒量子状态准备
Fast Black-Box Quantum State Preparation
论文作者
论文摘要
量子状态制备是其他高级量子算法（例如哈密顿模拟）或将分布加载到用于使用的量子设备中的重要成分。在优化任务（例如机器学习）的背景下。从Grover在2000年设计的通用“黑匣子”方法开始，该方法采用振幅放大来由Oracle计算出的负载系数，在桑德斯等人的工作中避免了几乎所有制备阶段的所有疗法。 在这项工作中，我们构建了一种优化的黑匣子状态加载方案，使用该方案可以使用各种重要系数的系数加载速度要比$ O（\ sqrt n）$ rounds的振幅放大，最高可达$ o（1）$。我们通过算法的两个变体来实现这一目标。第一次使用Sanders等人对Oracle进行修改，该修改需要更少的Ancillas（$ \ log_2 g $ vs $ g+2 $在位精度$ G $中），并且在我们的算法中，每个振幅膨胀回合中的非克利福德操作较少。第二个利用相同的甲骨文，但每次放大回合的Ancillas（$ g+\ log_2g $）和非克利福德操作的成本略有增加。随着振幅扩增的数量作为乘法因子进入，与先前的方法相比，我们的黑匣子状态加载方案可以达到指数加速。这种加速超出了黑匣子外壳。
Quantum state preparation is an important ingredient for other higher-level quantum algorithms, such as Hamiltonian simulation, or for loading distributions into a quantum device to be used e.g. in the context of optimization tasks such as machine learning. Starting with a generic "black box" method devised by Grover in 2000, which employs amplitude amplification to load coefficients calculated by an oracle, there has been a long series of results and improvements with various additional conditions on the amplitudes to be loaded, culminating in Sanders et al.'s work which avoids almost all arithmetic during the preparation stage. In this work, we construct an optimized black box state loading scheme with which various important sets of coefficients can be loaded significantly faster than in $O(\sqrt N)$ rounds of amplitude amplification, up to only $O(1)$ many. We achieve this with two variants of our algorithm. The first employs a modification of the oracle from Sanders et al., which requires fewer ancillas ($\log_2 g$ vs $g+2$ in the bit precision $g$), and fewer non-Clifford operations per amplitude amplification round within the context of our algorithm. The second utilizes the same oracle, but at slightly increased cost in terms of ancillas ($g+\log_2g$) and non-Clifford operations per amplification round. As the number of amplitude amplification rounds enters as multiplicative factor, our black box state loading scheme yields an up to exponential speedup as compared to prior methods. This speedup translates beyond the black box case.
