2019/10/31 by Jessica Lemieux, Bettina Heim, David Poulin +2 · 1 citation
Physics and Astronomy · #quant-ph
paper · pdf · doi:10.22331/q-2020-06-29-287
published as Quantum 4, 287 (2020)
arxiv created 2020/06/25 · arxiv updated 2020/07/01
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.