Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, Matthias Troyer
Abstract
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. We thus reformulate the quantum walk, circumventing its implementation altogether by closely following 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.
Topics & Concepts
Quantum walkQuantum algorithmQuantum computerHeuristicQuantumAlgorithmQuantum phase estimation algorithmQuantum circuitComputer scienceQuantum sortQuantization (signal processing)Quantum Fourier transformOracleContext (archaeology)MathematicsPolynomialTheoretical computer scienceQuantum networkQuantum informationQuantum error correctionElectronic circuitQuantum operationQuantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsQuantum Information and Cryptography