  Lattice QCD in the strong coupling regime can be formulated in dual variables
which are integer-valued. It can be efficiently simulated for modest finite
temperatures and finite densities via the worm algorithm, circumventing the
finite density sign problem in this regime. However, the low temperature regime
is more expensive to address. As the partition function is solely expressed in
terms of integers, it can be cast as a combinatorial optimization problem that
can be solved on a quantum annealer. We will first explain the setup of the
system we want to study, and then present its reformulation suitable for a
quantum annealer, and in particular the D-Wave. As a proof of concept, we
present first results obtained on D-Wave for gauge group $U(1)$ and $U(3)$, and
outline the next steps towards gauge groups $SU(3)$. We find that in addition,
histogram reweighting greatly improves the accuracy of our observables when
compared to analytic results.
