© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2112.02190 · Quantum Science and Technology

Markov chain Monte Carlo enhanced variational quantum algorithms

Taylor L. Patti, Omar Shehab, Khadijeh Najafi, Susanne F. Yelin

Published Dec 2, 2022• 16 citations

Abstract

Abstract Variational quantum algorithms have the potential for significant impact on high-dimensional optimization, with applications in classical combinatorics, quantum chemistry, and condensed matter. Nevertheless, the optimization landscape of these algorithms is generally nonconvex, leading the algorithms to converge to local, rather than global, minima and the production of suboptimal solutions. In this work, we introduce a variational quantum algorithm that couples classical Markov chain Monte Carlo techniques with variational quantum algorithms, allowing the former to provably converge to global minima and thus assure solution quality. Due to the generality of our approach, it is suitable for a myriad of quantum minimization problems, including optimization and quantum state preparation. Specifically, we devise a Metropolis–Hastings method that is suitable for variational quantum devices and use it, in conjunction with quantum optimization, to construct quantum ensembles that converge to Gibbs states. These performance guarantees are derived from the ergodicity of our algorithm’s state space and enable us to place analytic bounds on its time-complexity. We demonstrate both the effectiveness of our technique and the validity of our analysis through quantum circuit simulations for MaxCut instances, solving these problems deterministically and with perfect accuracy, as well as large-scale quantum Ising and transverse field spin models of up to 50 qubits. Our technique stands to broadly enrich the field of variational quantum algorithms, improving and guaranteeing the performance of these promising, yet often heuristic, methods.

DOI: 10.1088/2058-9565/aca821

Related papers

Methods for non-variational heuristic quantum optimisation

Stuart Ferguson, Petros Wallden

Optimisation plays a central role in a wide range of scientific and industrial applications, and quantum computing has been widely proposed as a means to achieve computational advantages in this domain. To date, research into the design of noise-resilient quantum algorithms has been dominated by variational approaches, while alternatives remain relatively unexplored. In this work, we introduce a novel class of quantum optimisation heuristics that forgo this variational framework in favour of a hybrid quantum-classical approach built upon Markov Chain Monte Carlo (MCMC) techniques. We introduce Quantum-enhanced Simulated Annealing (QeSA) and Quantum-enhanced Parallel Tempering (QePT), before validating these heuristics on hard Sherrington-Kirkpatrick instances and demonstrate their superior scaling over classical benchmarks. These algorithms are expected to exhibit inherent robustness to noise and support parallel execution across both quantum and classical resources with only classical communication required. As such, they offer a scalable and potentially competitive route toward solving large-scale optimisation problems with near-term quantum devices.

quant-pharXiv:2602.01353•Feb 3, 2026•0 citations

A Variational Quantum Monte Carlo Investigation for Nonconvex Optimization

Vasilis Skarlatos, Konstantinos P. Prousalis, Nikos Konofaos

We present a deterministic investigation of Variational Quantum Monte Carlo optimization over discrete, exponentially large state spaces. By evaluating variational objectives and analytic gradients exactly through explicit summation, statistical sampling effects are avoided, enabling controlled study of smooth but highly nonconvex optimization landscapes. The framework is instantiated on small structured quantum systems with known exact optima, allowing direct validation of gradient implementations and optimization behavior. Using variational parameterization, gradient-based methods converge to the exact solution for systems of up to eight qubits, with energy deviations on the order of 10− 5 for small systems and 10− 9 for larger ones. The resulting setup provides a compact, stochasticity-free reference for investigating variational objectives and optimization dynamics in discrete high-dimensional settings.

Pan-Hellenic Conference on Progress in Computing and Informatics (PCI)•Apr 24, 2026•0 citations

Quantum-enhanced Markov Chain Monte Carlo for Combinatorial Optimization

Kate V. Marshall, Daniel J. Egger, Michael Garn +4 more

Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.

quant-pharXiv:2602.06171•Feb 9, 2026•0 citations

Quantum-enhanced Markov chain Monte Carlo

David Layden, Guglielmo Mazzola, Ryan V. Mishmash +4 more

Sampling from complicated probability distributions is a hard computational problem arising in many fields, including statistical physics, optimization, and machine learning. Quantum computers have recently been used to sample from complicated distributions that are hard to sample from classically, but which seldom arise in applications. Here we introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications, which we implement on a superconducting quantum processor. The algorithm performs Markov chain Monte Carlo (MCMC), a popular iterative sampling technique, to sample from the Boltzmann distribution of classical Ising models. In each step, the quantum processor explores the model in superposition to propose a random move, which is then accepted or rejected by a classical computer and returned to the quantum processor, ensuring convergence to the desired Boltzmann distribution. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances, both in simulations and experiments. It therefore opens a new path for quantum computers to solve useful--not merely difficult--problems in the near term.

arXiv:2203.12497•Mar 23, 2022•0 citations

Variational Monte Carlo and the Quantum Enhanced Metropolis-Hastings Algorithm

Mishka Naicker, Mervlyn Moodley

Abstract This work explores adapting the classical Metropolis-Hastings algorithm into a quantum-enhanced framework to improve sampling efficiency in variational Monte Carlo. Utilizing variational Monte Carlo, and in particular the single-thread Monte Carlo method, we estimate the dominant eigenvalue of a symmetric 3 $$\times $$ × 3 matrix, serving as the toy model for the ground state energy of a three-level quantum system. We compare classical and hybrid quantum-classical implementations, where the latter employs the quantum enhanced Metropolis-Hastings algorithm. In a simulated environment, the hybrid version demonstrates faster convergence and improved estimator precision for this test case.

Quantum Information Processing•Jul 17, 2026•0 citations

Overcoming barriers to scalability in variational quantum Monte Carlo

Tianchen Zhao, Saibal De, Brian Chen +2 more

The variational quantum Monte Carlo (VQMC) method received significant attention in the recent past because of its ability to overcome the curse of dimensionality inherent in many-body quantum systems. Close parallels exist between VQMC and the emerging hybrid quantum-classical computational paradigm of variational quantum algorithms. VQMC overcomes the curse of dimensionality by performing alternating steps of Monte Carlo sampling from a parametrized quantum state followed by gradient-based optimization. While VQMC has been applied to solve high-dimensional problems, it is known to be difficult to parallelize, primarily owing to the Markov Chain Monte Carlo (MCMC) sampling step. In this work, we explore the scalability of VQMC when autoregressive models, with exact sampling, are used in place of MCMC. This approach can exploit distributed-memory, shared-memory and/or GPU parallelism in the sampling task without any bottlenecks. In particular, we demonstrate the GPU-scalability of VQMC for solving up to ten-thousand dimensional combinatorial optimization problems.

arXiv:2106.13308•Jun 24, 2021•0 citations

Abstract Variational quantum algorithms have the potential for significant impact on high-dimensional optimization, with applications in classical combinatorics, quantum chemistry, and condensed matter. Nevertheless, the optimization landscape of these algorithms is generally nonconvex, leading the algorithms to converge to local, rather than global, minima and the production of suboptimal solutions. In this work, we introduce a variational quantum algorithm that couples classical Markov chain Monte Carlo techniques with variational quantum algorithms, allowing the former to provably converge to global minima and thus assure solution quality. Due to the generality of our approach, it is suitable for a myriad of quantum minimization problems, including optimization and quantum state preparation. Specifically, we devise a Metropolis–Hastings method that is suitable for variational quantum devices and use it, in conjunction with quantum optimization, to construct quantum ensembles that converge to Gibbs states. These performance guarantees are derived from the ergodicity of our algorithm’s state space and enable us to place analytic bounds on its time-complexity. We demonstrate both the effectiveness of our technique and the validity of our analysis through quantum circuit simulations for MaxCut instances, solving these problems deterministically and with perfect accuracy, as well as large-scale quantum Ising and transverse field spin models of up to 50 qubits. Our technique stands to broadly enrich the field of variational quantum algorithms, improving and guaranteeing the performance of these promising, yet often heuristic, methods.

Optimisation plays a central role in a wide range of scientific and industrial applications, and quantum computing has been widely proposed as a means to achieve computational advantages in this domain. To date, research into the design of noise-resilient quantum algorithms has been dominated by variational approaches, while alternatives remain relatively unexplored. In this work, we introduce a novel class of quantum optimisation heuristics that forgo this variational framework in favour of a hybrid quantum-classical approach built upon Markov Chain Monte Carlo (MCMC) techniques. We introduce Quantum-enhanced Simulated Annealing (QeSA) and Quantum-enhanced Parallel Tempering (QePT), before validating these heuristics on hard Sherrington-Kirkpatrick instances and demonstrate their superior scaling over classical benchmarks. These algorithms are expected to exhibit inherent robustness to noise and support parallel execution across both quantum and classical resources with only classical communication required. As such, they offer a scalable and potentially competitive route toward solving large-scale optimisation problems with near-term quantum devices.

We present a deterministic investigation of Variational Quantum Monte Carlo optimization over discrete, exponentially large state spaces. By evaluating variational objectives and analytic gradients exactly through explicit summation, statistical sampling effects are avoided, enabling controlled study of smooth but highly nonconvex optimization landscapes. The framework is instantiated on small structured quantum systems with known exact optima, allowing direct validation of gradient implementations and optimization behavior. Using variational parameterization, gradient-based methods converge to the exact solution for systems of up to eight qubits, with energy deviations on the order of 10− 5 for small systems and 10− 9 for larger ones. The resulting setup provides a compact, stochasticity-free reference for investigating variational objectives and optimization dynamics in discrete high-dimensional settings.

Quantum computing offers an alternative paradigm for addressing combinatorial optimization problems compared to classical computing. Despite recent hardware improvements, the execution of empirical quantum optimization experiments at scales known to be hard for state-of-the-art classical solvers is not yet in reach. In this work, we offer a different way to approach combinatorial optimization with near-term quantum computing. Motivated by the promising results observed in using quantum-enhanced Markov chain Monte Carlo (QeMCMC) for approximating complicated probability distributions, we combine ideas of sampling from the device with QeMCMC together with warm-starting and parallel tempering, in the context of combinatorial optimization. We demonstrate empirically that our algorithm recovers the global optima for instances of the Maximum Independent Set problem (MIS) up to 117 decision variables using 117 qubits on IBM quantum hardware. We show early evidence of a scaling advantage of our algorithm compared to similar classical methods for the chosen instances of MIS. MIS is practically relevant across domains like financial services and molecular biology, and, in some cases, already difficult to solve to optimality classically with only a few hundred decision variables.

Sampling from complicated probability distributions is a hard computational problem arising in many fields, including statistical physics, optimization, and machine learning. Quantum computers have recently been used to sample from complicated distributions that are hard to sample from classically, but which seldom arise in applications. Here we introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications, which we implement on a superconducting quantum processor. The algorithm performs Markov chain Monte Carlo (MCMC), a popular iterative sampling technique, to sample from the Boltzmann distribution of classical Ising models. In each step, the quantum processor explores the model in superposition to propose a random move, which is then accepted or rejected by a classical computer and returned to the quantum processor, ensuring convergence to the desired Boltzmann distribution. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances, both in simulations and experiments. It therefore opens a new path for quantum computers to solve useful--not merely difficult--problems in the near term.

Abstract This work explores adapting the classical Metropolis-Hastings algorithm into a quantum-enhanced framework to improve sampling efficiency in variational Monte Carlo. Utilizing variational Monte Carlo, and in particular the single-thread Monte Carlo method, we estimate the dominant eigenvalue of a symmetric 3

\times

× 3 matrix, serving as the toy model for the ground state energy of a three-level quantum system. We compare classical and hybrid quantum-classical implementations, where the latter employs the quantum enhanced Metropolis-Hastings algorithm. In a simulated environment, the hybrid version demonstrates faster convergence and improved estimator precision for this test case.

The variational quantum Monte Carlo (VQMC) method received significant attention in the recent past because of its ability to overcome the curse of dimensionality inherent in many-body quantum systems. Close parallels exist between VQMC and the emerging hybrid quantum-classical computational paradigm of variational quantum algorithms. VQMC overcomes the curse of dimensionality by performing alternating steps of Monte Carlo sampling from a parametrized quantum state followed by gradient-based optimization. While VQMC has been applied to solve high-dimensional problems, it is known to be difficult to parallelize, primarily owing to the Markov Chain Monte Carlo (MCMC) sampling step. In this work, we explore the scalability of VQMC when autoregressive models, with exact sampling, are used in place of MCMC. This approach can exploit distributed-memory, shared-memory and/or GPU parallelism in the sampling task without any bottlenecks. In particular, we demonstrate the GPU-scalability of VQMC for solving up to ten-thousand dimensional combinatorial optimization problems.