Grover’s search with learning oracle for constrained binary optimization problems

Grover adaptive search (GAS) for binary optimization (BO) problems is a quantum algorithm for iteratively finding optimal solutions using Grover’s search algorithm. However, in GAS, iterative oracle constructions are needed, and a high computational demand is required. In this study, we introduce a quantum generative model-based learning oracle and present Grover’s search with a learning oracle (GLO) for BO problems. In the GLO, a learning oracle is constructed by a parameterized unitary. Its training is performed by a hybrid quantum-classical learning framework using the cost function involving the solution constraints and the evolution strategy as a gradient-free optimization algorithm. The GLO is trained to obtain optimal solutions with probability one. The experiments conducted on the constrained BO problems demonstrate significant decreases in the number of cost function callings (query complexity) compared to GAS. Furthermore, we also discuss the effects of the entanglers (controlled Pauli Z or X gates) of the learning oracle using a model capacity measure (i.e., effective dimension). The entanglers improve the training performance of the GLO (i.e., query complexity and search success rate). The obtained results indicate the efficiency and promise of our approach.