Ardelean Sebastian Mihai, Udrescu Mihai
Department of Computer and Information Technology, University Politehnica of Timisoara, Timisoara, Timis, Romania.
PeerJ Comput Sci. 2024 Aug 5;10:e2210. doi: 10.7717/peerj-cs.2210. eCollection 2024.
Quantum genetic algorithms (QGA) integrate genetic programming and quantum computing to address search and optimization problems. The standard strategy of the hybrid QGA approach is to add quantum resources to classical genetic algorithms (GA), thus improving their efficacy (, quantum optimization of a classical algorithm). However, the extent of such improvements is still unclear. Conversely, Reduced Quantum Genetic Algorithm (RQGA) is a fully quantum algorithm that reduces the GA search for the best fitness in a population of potential solutions to running Grover's algorithm. Unfortunately, RQGA finds the best fitness value and its corresponding chromosome (, the solution or one of the solutions of the problem) in exponential runtime, O(2), where is the number of qubits in the individuals' quantum register. This article introduces a novel QGA optimization strategy, namely a classical optimization of a fully quantum algorithm, to address the RQGA complexity problem. Accordingly, we control the complexity of the RQGA algorithm by selecting a limited number of qubits in the individuals' register and fixing the remaining ones as classical values of '0' and '1' with a genetic algorithm. We also improve the performance of RQGA by discarding unfit solutions and bounding the search only in the area of valid individuals. As a result, our Hybrid Quantum Algorithm with Genetic Optimization (HQAGO) solves search problems in O(2) oracle queries, where is the number of fixed classical bits in the individuals' register.
量子遗传算法（QGA）将遗传编程与量子计算相结合，以解决搜索和优化问题。混合QGA方法的标准策略是将量子资源添加到经典遗传算法（GA）中，从而提高其效率（即对经典算法进行量子优化）。然而，这种改进的程度仍不明确。相反，简化量子遗传算法（RQGA）是一种完全量子算法，它将GA在潜在解群体中寻找最佳适应度的过程简化为运行格罗弗算法。不幸的是，RQGA在指数运行时间O(2^n)内找到最佳适应度值及其相应的染色体（即问题的解或其中一个解），其中n是个体量子寄存器中的量子比特数。本文介绍了一种新颖的QGA优化策略，即对完全量子算法进行经典优化，以解决RQGA的复杂性问题。因此，我们通过在个体寄存器中选择有限数量的量子比特，并使用遗传算法将其余的固定为“0”和“1”的经典值，来控制RQGA算法的复杂性。我们还通过丢弃不适合的解并仅在有效个体区域内限制搜索来提高RQGA的性能。结果，我们的遗传优化混合量子算法（HQAGO）在O(2^k)次预言机查询中解决搜索问题，其中k是个体寄存器中固定经典比特的数量。
