$SU(N_c)$ gauge theories in the strong coupling limit can be described by integer variables representing monomers, dimers and baryon loops. We demonstrate how the D-wave quantum
annealer can perform importance sampling on $U(N_c)$ gauge theory in the strong coupling formulation of this theory. In addition to causing a sign problem in importance sampling, baryon loops induce a complex QUBO matrix which cannot be optimized by the D-Wave annealer. Instead we show that simulating the sign-problem free quenched action on the
D-Wave is sufficient when combined with a sign reweighting method. As the first test on $SU(3)$ gauge theory, we simulate on $2 \times 2$ lattice and compare the results with its analytic solutions.