  We present a detailed circuit implementation of Szegedy's quantization of the
Metropolis-Hastings walk. This quantum walk is usually defined with respect to
an oracle. We find that a direct implementation of this oracle requires costly
arithmetic operations and thus reformulate the quantum walk in a way that
circumvents the implementation of that specific oracle and which closely
follows the classical Metropolis-Hastings walk. We also present heuristic
quantum algorithms that use the quantum walk in the context of discrete
optimization problems and numerically study their performances. Our numerical
results indicate polynomial quantum speedups in heuristic settings.
