A computer implemented method includes receiving, by a control system, an optimization problem expressed as a MWIS on a problem graph. Then encoding the MWIS problem into an energy spectrum of a problem Hamiltonian. Also, determining an XX-driver graph based on an identified independent-cliques (IC), where the edges in the XX-driver graph are the edges between partites in each clique of the IC. Also, determining XX-coupler strengths associated with the XX-driver graph, and specifying a non-stoquastic driver Hamiltonian based on the XX-driver graph and the associated XX-coupler strengths. Also, initializing and programming a time-dependent non-stoquastic system Hamiltonian of the quantum annealing hardware using determined values of parameters included in the problem Hamiltonian and determined values of parameters included in the non-stoquastic driver Hamiltonian. Furthermore, implementing, by the hardware, a quantum annealing schedule, and receiving an output representing eigen-states of the system Hamiltonian and corresponding energy values.