Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm

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 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.

References in corpus (15)

• Elementary gates for quantum computation
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Defining and detecting quantum speedup
• Quantum Metropolis Sampling
• Search via Quantum Walk
• Quantum Simulations of Classical Annealing Processes
• A Quantum-Quantum Metropolis Algorithm
• Simulating chemistry efficiently on fault-tolerant quantum computers
• The methodology of resonant equiangular composite quantum gates
• JANUS: an FPGA-based System for High Performance Scientific Computing
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Efficient synthesis of probabilistic quantum circuits with fallback
• Reconfigurable computing for Monte Carlo simulations: results and prospects of the Janus project
• Resource estimate for quantum many-body ground-state preparation on a quantum computer

Cited by in corpus (32)

• Quantum computing for finance
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
• Quantum-enhanced Markov chain Monte Carlo
• Prospects of Quantum Computing for Molecular Sciences
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Quantum walk approach to simulating parton showers
• Quantum computing for chemistry and physics applications from a Monte Carlo perspective
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• Collider Events on a Quantum Computer
• Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
• The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
• Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
• Density functionals and Kohn-Sham potentials with minimal wavefunction preparations on a quantum computer
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• From quantum-enhanced to quantum-inspired Monte Carlo
• Discrete-time Semiclassical Szegedy Quantum Walks
• SQUWALS: A Szegedy QUantum WALks Simulator
• Randomized semi-quantum matrix processing
• Quantum-assisted variational Monte Carlo
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Quantum Bayesian Inference with Renormalization for Gravitational Waves
• Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption
• Complex-Phase Extensions of Szegedy Quantum Walk on Graphs
• Quantum Algorithm for Testing Graph Completeness
• Quantum Speedup for Nonreversible Markov Chains
• Quantum walks advantage on the dihedral group for uniform sampling problem
• Many-Fermion Simulation from the Contracted Quantum Eigensolver without Fermionic Encoding of the Wave Function