论文标题
使用Grover算法的二项式版本优化量子搜索
Optimizing Quantum Search with a Binomial Version of Grover's Algorithm
论文作者
论文摘要
振幅放大 - Grover搜索算法的关键组成部分 - 使用迭代方法系统地增加一个或多个目标状态的概率。我们提出了新的策略来通过将状态划分为阶级来增强放大程序的新策略，在放大之前或放大期间，其概率在不同的水平上增加。分区过程基于二项式分布。如果预先知道搜索目标状态所属的类，则与标准版本相比，幅度放大算法中的迭代次数可以大大减少。在更有可能的情况下，相关类未提前知道，可以在运行时配置它们的选择，也可以采用随机方法，类似于经典算法，例如二进制搜索。特别是，我们在先前引入的量子词典模式的上下文中应用此方法，其中键和值在两个单独的寄存器中编码，并且值编码方法与密钥寄存器中使用的叠加类型无关。我们认为这种类型的结构是搜索的自然设置。我们通过在Honeywell系统模型H0陷阱离子量子计算机上获得的实验结果来确认我们的新方法的有效性。
Amplitude Amplification -- a key component of Grover's Search algorithm -- uses an iterative approach to systematically increase the probability of one or multiple target states. We present novel strategies to enhance the amplification procedure by partitioning the states into classes, whose probabilities are increased at different levels before or during amplification. The partitioning process is based on the binomial distribution. If the classes to which the search target states belong are known in advance, the number of iterations in the Amplitude Amplification algorithm can be drastically reduced compared to the standard version. In the more likely case in which the relevant classes are not known in advance, their selection can be configured at run time, or a random approach can be employed, similar to classical algorithms such as binary search. In particular, we apply this method in the context of our previously introduced Quantum Dictionary pattern, where keys and values are encoded in two separate registers, and the value-encoding method is independent of the type of superposition used in the key register. We consider this type of structure to be the natural setup for search. We confirm the validity of our new approach through experimental results obtained on real quantum hardware, the Honeywell System Model H0 trapped-ion quantum computer.
