  An earlier work [18] proposes a method for solving the Lagrangian dual of a
constrained binary quadratic programming problem via quantum adiabatic
evolution using an outer approximation method. This should be an efficient
prescription for solving the Lagrangian dual problem in the presence of an
ideally noise-free quantum adiabatic system. However, current implementations
of quantum annealing systems demand methods that are efficient at handling
possible sources of noise. In this paper, we consider a subgradient method for
finding an optimal primal-dual pair for the Lagrangian dual of a constrained
binary polynomial programming problem. We then study the quadratic stable set
(QSS) problem as a case study. We see that this method applied to the QSS
problem can be viewed as an instance-dependent penalty-term approach that
avoids large penalty coefficients. Finally, we report our experimental results
of using the D-Wave 2X quantum annealer and conclude that our approach helps
this quantum processor to succeed more often in solving these problems compared
to the usual penalty-term approaches.
