Combinatorial optimization problems aim to find the configuration of inputs that minimizes a cost function and can be employed in many real-world applications. Most of them are known to be NP-complete or NP-hard, thus classically solvable with exponential complexity. Quadratic Unconstrained Binary Optimization (QUBO) formulation can express them in a format suitable for quantum solvers, which can reduce the computational complexity by exploiting the quantum principles. One of the most recent solvers, the Grover Adaptive Search (GAS), is a successive approximation method that iteratively shifts the cost function whenever a negative value is obtained until the minimum is achieved. It encodes the function in a quantum state as key-value pairs and exploits Grover’s Search (GS), a quantum routine able to explore an unordered dataset with lower complexity than the classical counterpart, for obtaining negative samples.