Quantum Acceleration of Black-Box Pseudo-Boolean Optimization Algorithms
该文研究量子进化算法，通过动态突变率策略加速伪布尔函数优化，在NEEDLE问题上达到量子最优，并针对LEADINGONES和ONEMAX问题提出超越经典算法的量子算法。
The <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1+1)$ </tex-math></inline-formula> quantum evolutionary algorithm [<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1+1)$ </tex-math></inline-formula> QEA] uses quantum probability amplification to accelerate the classical <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1+1)$ </tex-math></inline-formula> evolutionary algorithm [<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1+1)$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1+1)$ </tex-math></inline-formula> QEA, leveraging the guarantees the fixed-point amplitude amplification algorithm gives to adjust the mutation rate dynamically [<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1+1)$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1+1)$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-dimensional LEADINGONES problem with at most <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> 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.