Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2506.01335 · PRX Quantum

Neural-Network-Assisted Monte Carlo Sampling Trained by Quantum Approximate Optimization Algorithm

Yuichiro Nakano, Ken N. Okada, Keisuke Fujii

Published Jan 6, 2026• 1 citation
arXivHTMLPDF

Abstract

Sampling problems are widely regarded as the task for which quantum computers can most readily provide a quantum advantage. Leveraging this feature, the quantum-enhanced Markov chain Monte Carlo [Layden , Nature 619, 282–287 (2023)] has been proposed recently, where sampling from a quantum computer is used as a proposal distribution and convergence to a target distribution is accelerated. However, guaranteeing convergence to the target distribution typically forces one to impose restrictive symmetry constraints on the quantum circuit, which makes it hard to design good proposal distributions and prevents making full use of the advantage of a quantum computer. We explore a hybrid quantum-classical Markov chain Monte Carlo framework that combines a quantum circuit with a generative neural sampler (GNS). The GNS is trained on quantum samples and acts as a classical surrogate to efficiently emulate quantum outputs, thereby lifting circuit constraints. We apply this method to Boltzmann sampling of spin glasses using proposals trained with a quantum approximate optimization algorithm circuit. This approach outperforms conventional methods, showing a polynomial speedup (over cubic) in spectral gap compared with uniform proposals. Notably, it maintains similar acceleration even without parameter optimization. These results establish the method as a viable sampling-based quantum algorithm for noisy intermediate-scale quantum devices and highlight its potential for solving practical problems with quantum computation.

DOI
10.1103/9nhx-5pym

Related papers

Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems

Yuya Kawamata, Yuichiro Nakano, Keisuke Fujii

Sampling problems are promising candidates for demonstrating quantum advantage, and one approach known as quantum-enhanced Markov chain Monte Carlo [Layden, D. et al., Nature 619, 282-287 (2023)] uses quantum samples as a proposal distribution to accelerate convergence to a target distribution. On the other hand, many practical problems are large-scale and constrained, making it difficult to construct efficient proposal distributions in classical methods and slowing down MCMC mixing. In this work, we propose a divide-and-conquer neural network surrogate framework for quantum sampling to accelerate MCMC under fixed Hamming weight constraints. Our method divides the interaction graph for an Ising problem into subgraphs, generates samples using QAOA for those subproblems with an XY mixer, and trains neural network surrogates conditioned on the Hamming weight to provide proposal distributions for each subset while preserving the constraint. In numerical experiments of Boltzmann sampling on 3-regular graphs, our method consistently accelerated mixing as the system size $N$ increased, with average improvements in the autocorrelation decay rate constant by speedup factors of about $20.3$ and $7.6$ over classical pair-flip methods based on nearest-neighbor and non-nearest-neighbor exchanges, respectively. We also applied the method to an MNIST feature mask optimization problem with $N=784$, obtaining faster energy convergence and a $2.03\%$ higher classification accuracy. These results show that our method enables efficient and scalable MCMC and can outperform classical methods for practical applications on NISQ devices.

quant-pharXiv:2604.20701•Apr 23, 2026•0 citations

Bounding speedup of quantum-enhanced Markov chain Monte Carlo

Alev Orfi, Dries Sels

Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [Layden, D. et al. Nature 619, 282-287 (2023)] proposed a quantum-enhanced Markov chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.

arXiv:2403.03087•Mar 5, 2024•0 citations

Quantum-Assisted Variational Monte Carlo

Longfei Chang, Zhendong Li, Wei‐Hai Fang

Solving the ground state of quantum many-body systems remains a fundamental challenge in physics and chemistry. Recent advancements in quantum hardware have opened new avenues for addressing this challenge. Inspired by the quantum-enhanced Markov chain Monte Carlo (QeMCMC) algorithm, which was originally designed for sampling the Boltzmann distribution of classical spin models using quantum computers, we introduce a quantum-assisted variational Monte Carlo (QA-VMC) algorithm for solving the ground state of quantum many-body systems by adapting QeMCMC to sample the distribution of a (neural-network) wave function in VMC. The central question is whether such a quantum-assisted proposal can potentially offer a computational advantage over classical methods. Through numerical investigations for the Fermi-Hubbard model and molecular systems, we demonstrate that the quantum-assisted proposal exhibits larger absolute spectral gaps and reduced autocorrelation times compared to conventional classical proposals, leading to more efficient sampling and faster convergence to the ground state in VMC as well as a more accurate and precise estimation of physical observables. This advantage is especially pronounced for specific parameter ranges, where the ground-state configurations are more concentrated in some configurations separated by large Hamming distances. Our results underscore the potential of quantum-assisted algorithms to enhance classical variational methods for solving the ground state of quantum many-body systems.

arXiv:2502.20799•Precision Chemistry•Jun 7, 2025•4 citations

Bounding the speedup of the quantum-enhanced Markov-chain Monte Carlo algorithm

Alev Orfi, Dries Sels

Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [D. Layden et al., Nature (London) 619, 282 (2023).] proposed a quantum-enhanced Markov-chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.

Physical Review A•Nov 12, 2024•11 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 dynamical Hamiltonian Monte Carlo

Owen Lockwood, Peter Weiß, Filip Aronshtein +1 more

One of the open challenges in quantum computing is to find meaningful and practical methods to leverage quantum computation to accelerate classical machine-learning workflows. A ubiquitous problem in machine-learning workflows is sampling from probability distributions that we only have access to via their log probability. To this end, we extend the well-known Hamiltonian Monte Carlo (HMC) method for Markov chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner as a proposal function. Our new algorithm, Quantum Dynamical Hamiltonian Monte Carlo (QD-HMC), replaces the classical symplectic integration proposal step with simulations of quantum-coherent continuous-space dynamics on digital or analog quantum computers. We show that QD-HMC maintains key characteristics of HMC, such as maintaining the detailed balanced condition with momentum inversion, while also having the potential for polynomial speedups over its classical counterpart in certain scenarios. As sampling is a core subroutine in many forms of probabilistic inference, and MCMC in continuously parametrized spaces covers a large class of potential applications, this work widens the areas of applicability of quantum devices. Published by the American Physical Society 2024

arXiv:2403.01775•Physical Review Research•Aug 6, 2024•13 citations
Sampling problems are widely regarded as the task for which quantum computers can most readily provide a quantum advantage. Leveraging this feature, the quantum-enhanced Markov chain Monte Carlo [Layden , Nature 619, 282–287 (2023)] has been proposed recently, where sampling from a quantum computer is used as a proposal distribution and convergence to a target distribution is accelerated. However, guaranteeing convergence to the target distribution typically forces one to impose restrictive symmetry constraints on the quantum circuit, which makes it hard to design good proposal distributions and prevents making full use of the advantage of a quantum computer. We explore a hybrid quantum-classical Markov chain Monte Carlo framework that combines a quantum circuit with a generative neural sampler (GNS). The GNS is trained on quantum samples and acts as a classical surrogate to efficiently emulate quantum outputs, thereby lifting circuit constraints. We apply this method to Boltzmann sampling of spin glasses using proposals trained with a quantum approximate optimization algorithm circuit. This approach outperforms conventional methods, showing a polynomial speedup (over cubic) in spectral gap compared with uniform proposals. Notably, it maintains similar acceleration even without parameter optimization. These results establish the method as a viable sampling-based quantum algorithm for noisy intermediate-scale quantum devices and highlight its potential for solving practical problems with quantum computation.
Sampling problems are promising candidates for demonstrating quantum advantage, and one approach known as quantum-enhanced Markov chain Monte Carlo [Layden, D. et al., Nature 619, 282-287 (2023)] uses quantum samples as a proposal distribution to accelerate convergence to a target distribution. On the other hand, many practical problems are large-scale and constrained, making it difficult to construct efficient proposal distributions in classical methods and slowing down MCMC mixing. In this work, we propose a divide-and-conquer neural network surrogate framework for quantum sampling to accelerate MCMC under fixed Hamming weight constraints. Our method divides the interaction graph for an Ising problem into subgraphs, generates samples using QAOA for those subproblems with an XY mixer, and trains neural network surrogates conditioned on the Hamming weight to provide proposal distributions for each subset while preserving the constraint. In numerical experiments of Boltzmann sampling on 3-regular graphs, our method consistently accelerated mixing as the system size NNN increased, with average improvements in the autocorrelation decay rate constant by speedup factors of about 20.320.320.3 and 7.67.67.6 over classical pair-flip methods based on nearest-neighbor and non-nearest-neighbor exchanges, respectively. We also applied the method to an MNIST feature mask optimization problem with N=784N=784N=784, obtaining faster energy convergence and a 2.03%2.03\%2.03% higher classification accuracy. These results show that our method enables efficient and scalable MCMC and can outperform classical methods for practical applications on NISQ devices.
Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [Layden, D. et al. Nature 619, 282-287 (2023)] proposed a quantum-enhanced Markov chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.
Solving the ground state of quantum many-body systems remains a fundamental challenge in physics and chemistry. Recent advancements in quantum hardware have opened new avenues for addressing this challenge. Inspired by the quantum-enhanced Markov chain Monte Carlo (QeMCMC) algorithm, which was originally designed for sampling the Boltzmann distribution of classical spin models using quantum computers, we introduce a quantum-assisted variational Monte Carlo (QA-VMC) algorithm for solving the ground state of quantum many-body systems by adapting QeMCMC to sample the distribution of a (neural-network) wave function in VMC. The central question is whether such a quantum-assisted proposal can potentially offer a computational advantage over classical methods. Through numerical investigations for the Fermi-Hubbard model and molecular systems, we demonstrate that the quantum-assisted proposal exhibits larger absolute spectral gaps and reduced autocorrelation times compared to conventional classical proposals, leading to more efficient sampling and faster convergence to the ground state in VMC as well as a more accurate and precise estimation of physical observables. This advantage is especially pronounced for specific parameter ranges, where the ground-state configurations are more concentrated in some configurations separated by large Hamming distances. Our results underscore the potential of quantum-assisted algorithms to enhance classical variational methods for solving the ground state of quantum many-body systems.
Sampling tasks are a natural class of problems for quantum computers due to the probabilistic nature of the Born rule. Sampling from useful distributions on noisy quantum hardware remains a challenging problem. A recent paper [D. Layden et al., Nature (London) 619, 282 (2023).] proposed a quantum-enhanced Markov-chain Monte Carlo algorithm where moves are generated by a quantum device and accepted or rejected by a classical algorithm. While this procedure is robust to noise and control imperfections, its potential for quantum advantage is unclear. Here we show that there is no speedup over classical sampling on a worst-case unstructured sampling problem. We present an upper bound to the Markov gap that rules out a speedup for any unital quantum proposal.
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.
One of the open challenges in quantum computing is to find meaningful and practical methods to leverage quantum computation to accelerate classical machine-learning workflows. A ubiquitous problem in machine-learning workflows is sampling from probability distributions that we only have access to via their log probability. To this end, we extend the well-known Hamiltonian Monte Carlo (HMC) method for Markov chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner as a proposal function. Our new algorithm, Quantum Dynamical Hamiltonian Monte Carlo (QD-HMC), replaces the classical symplectic integration proposal step with simulations of quantum-coherent continuous-space dynamics on digital or analog quantum computers. We show that QD-HMC maintains key characteristics of HMC, such as maintaining the detailed balanced condition with momentum inversion, while also having the potential for polynomial speedups over its classical counterpart in certain scenarios. As sampling is a core subroutine in many forms of probabilistic inference, and MCMC in continuously parametrized spaces covers a large class of potential applications, this work widens the areas of applicability of quantum devices. Published by the American Physical Society 2024