混合量子搜索与基因算法优化

量子遗传算法（QGA）结合了遗传编程和量子计算，以解决搜索和优化问题。混合QGA方法的标准策略是向经典遗传算法（GA）添加量子资源，从而提高其效率（即对经典算法的量子优化）。然而，这种改进的程度仍然不清楚。相反，简化量子遗传算法（RQGA）是一种完全的量子算法，它通过运行Grover算法来减少GA在潜在解决方案人群中寻找最佳适应值的过程。不幸的是，RQGA在指数时间内找到最佳适应值及其对应的染色体（即问题的解决方案或其中一个解决方案），其运行时间为O(2 n/2)，其中n是个体量子寄存器中的量子位数。本文介绍了一种新颖的QGA优化策略，即对完全量子算法的经典优化，以解决RQGA的复杂性问题。因此，我们通过在个体寄存器中选择有限数量的量子位并使用遗传算法将其余的固定为经典值'0'和'1'来控制RQGA算法的复杂性。我们还通过去除不适合的解决方案并将搜索限制在有效个体的区域来提高RQGA的性能。因此，我们的混合量子算法与基因优化（HQAGO）在O(2 (n−k)/2)的oracle查询中解决搜索问题，其中k是个体寄存器中固定的经典位数。