Quantum Metropolis Solver: A Quantum Walks Approach to Optimization Problems

Abstract

The efficient resolution of optimization problems is one of the key issues in today's industry. This task relies mainly on classical algorithms that present scalability problems and processing limitations. Quantum computing has emerged to challenge these types of problems. In this paper, we focus on the Metropolis-Hastings quantum algorithm that is based on quantum walks. We use this algorithm to build a quantum software tool called Quantum Metropolis Solver (QMS). We validate QMS with the N-Queen problem to show a potential quantum advantage in an example that can be easily extrapolated to an Artificial Intelligence domain. We carry out different simulations to validate the performance of QMS and its configuration.

RevTex 4.2, 6 color figures, 4 tables

References in corpus (1)

• Quantum Simulations of Classical Annealing Processes

Cited by in corpus (8)

• Parameter Estimation of Gravitational Waves with a Quantum Metropolis Algorithm
• SQUWALS: A Szegedy QUantum WALks Simulator
• Quantum Bayesian Inference with Renormalization for Gravitational Waves
• Implementing Semiclassical Szegedy Walks in Classical-Quantum Circuits for Homomorphic Encryption
• Quantum Algorithm for Testing Graph Completeness
• Complex-Phase Extensions of Szegedy Quantum Walk on Graphs
• Quantum Speedups for Multiproposal MCMC
• Complexity for one-dimensional discrete time quantum walk circuits