Quantum Annealing with Inequality Constraints: The Set Cover Problem

Quantum annealing is a promising method for solving hard optimization problems by transforming them into quadratic unconstrained binary optimization (QUBO) problems. However, when constraints are involved, particularly multiple inequality constraints, incorporating them into the objective function poses challenges. In this paper, the authors present two novel approaches for solving problems with multiple inequality constraints on a quantum annealer and apply them to the set cover problem (SCP). The first approach uses the augmented Lagrangian method to represent the constraints, while the second approach employs a higher-order binary optimization (HUBO) formulation. The experiments show that both approaches outperform the standard approach for solving the SCP on the D-Wave Advantage quantum annealer. The HUBO formulation performs slightly better than the augmented Lagrangian method in solving the SCP, but its scalability in terms of embeddability in the quantum chip is worse. The results demonstrate that the proposed augmented Lagrangian and HUBO methods can successfully implement a large number of inequality constraints, making them applicable to a broad range of constrained problems beyond the SCP. Quantum annealing is a promising method for solving hard optimization problems if they can be formulated as quadratic unconstrained binary optimization problems. Most problems of practical interest do include constraints, however, and this paper proposes two methods for dealing with multiple inequality constraints that are more accurate than the existing ones, and applies them to the set cover problem.image