Engineering Grover Adaptive Search: Exploring the Degrees of Freedom for Efficient QUBO Solving

作     者：Giuffrida, Luigi Volpe, Deborah Cirillo, Giovanni Amedeo Zamboni, Maurizio Turvani, Giovanna 

作者机构：Politecn Torino Dept Elect & Telecommun I-10129 Turin Italy STMicroelectronics I-20007 Cornaredo Italy 

出 版 物：《IEEE JOURNAL ON EMERGING AND SELECTED TOPICS IN CIRCUITS AND SYSTEMS》 (IEEE J. Emerg. Sel. Top. Circuits Syst.)

年 卷 期：2022年第12卷第3期

页      面：614-623页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 

主　　题：Quantum computing Cost function Computers Search problems Task analysis Quantum circuit Optimal scheduling Grover search Grover adaptive search hybrid quantum-classical algorithms optimization problems quadratic unconstrained binary optimization cost function quantum dictionary 

摘      要：Quantum computers have the potential to solve Quadratic Unconstrained Binary Optimization (QUBO) problems with lower computational complexity than classical ones. Considering the current limitations of quantum hardware, the joint use of classical and quantum paradigms could exploit both advantages. Quantum routines can make some complex tasks for classical computers feasible. For example, in the Grover Adaptive Search (GAS) procedure, the problem cost function is classically shifted iteratively, whenever a negative value is found through the quantum Grover Search (GS) algorithm, until the minimum is achieved. This quantum-classical approach is characterized by many degrees of freedom, e.g. the number of GS iterations in each call and the stop condition of the algorithm, which should be appropriately tuned for an effective and fast convergence to the optimal solution. The availability of software routines could permit the best management of the GAS parameters. This work proposes new mechanisms for GAS parameters management and compares them with the existing ones, like one available in the Qiskit framework. The proposed mechanisms can automatically arrange the parameters according to the algorithm evolution and their previous experience, thus ensuring a more frequent and faster achievement of the optimal solution. Even though these strategies can be further improved, the results are encouraging. The analysis is done to identify the best policy for different problems. It lays the foundation for designing an automatic toolchain for QUBO solving, which can obtain the best possible implementation of the GAS algorithm for each submitted problem.