Quantum Acceleration of Black-Box Pseudo-Boolean Optimization Algorithms

The$(1+1)$quantum evolutionary algorithm [$(1+1)$QEA] uses quantum probability amplification to accelerate the classical$(1+1)$evolutionary algorithm [$(1+1)$EA] for the optimization of pseudo-Boolean functions, which assign real-valued fitness to binary strings. However, determining the optimal mutation rate remains crucial to reducing the required number of function evaluations. To address this, we introduce a dynamic mutation rate strategy for the$(1+1)$QEA, leveraging the guarantees the fixed-point amplitude amplification algorithm gives to adjust the mutation rate dynamically [$(1+1)$QEAdyn]. We derive upper bounds on the number of fitness evaluations the strategy requires to solve well-known benchmark functions. Notably, we close the performance gap of the$(1+1)$QEA on the NEEDLE problem, matching the optimal performance possible in the quantum setting. Nevertheless, our results on ONEMAX and LEADINGONES lag behind known classical results. So, we delve into quantum black-box complexity, exploring the difficulty of problem-solving on a quantum computer without explicit problem knowledge. We introduce a quantum algorithm that solves the$n$-dimensional LEADINGONES problem with at most$n$evaluations. Additionally, we develop a quantum algorithm for the ONEMAX problem, requiring only one function evaluation. Both of these quantum algorithms surpass the capabilities of classical algorithms. Finally, we devise a quantum algorithm for solving the ONEMAX problem using only fitness comparisons and provide computational evidence that it still does so faster than any classical algorithm.