Accelerating MCMC with Quantum Walks: Design, Implementation, and Results

• URL: http://arxiv.org/abs/2504.12089v1
• Date: Wed, 16 Apr 2025 13:53:32 GMT
• Title: Accelerating MCMC with Quantum Walks: Design, Implementation, and Results
• Authors: Aingeru Ramos, Jose A. Pascual, Javier Navaridas,
• Abstract summary: We present the design and implementation of a novel MCMC algorithm based on the Discrete Quantum Walk (DQW) algorithm.<n>We demonstrate that it effectively captures the structure of the target distribution by leveraging quantum superposition.<n>In addition, we introduce a circuit extension that significantly improves convergence speed, which in turn enhances the scalability of the algorithm.
• Score: 3.004066195320147
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Markov Chain Monte Carlo (MCMC) methods are algorithms for sampling probability distributions, often applied to the Boltzmann distribution in physical and chemical models, such as protein folding and the Ising model. These methods enable the study of such systems by sampling their most probable states. However, sampling multidimensional and multimodal distributions with MCMC demands significant computational resources, leading to the development of techniques aimed at improving sampling efficiency. In this context, quantum computing, with its potential to accelerate classical methods, emerges as a promising solution to the sampling problem. In this work, we present the design and implementation of a novel MCMC algorithm (QMCMC) based on the Discrete Quantum Walk (DQW) algorithm. We test several Gaussian distributions, including mixtures and demonstrate that it effectively captures the structure of the target distribution by leveraging quantum superposition. In addition, we introduce a circuit extension that significantly improves convergence speed, which in turn enhances the scalability of the algorithm.

Related papers

• Quantum-assisted variational Monte Carlo [1.283555556182245]
  We introduce a quantum-assisted variational Monte Carlo (QA-VMC) algorithm for solving the ground state of quantum many-body systems.<n>We demonstrate that the quantum-assisted proposal exhibits larger absolute spectral gaps and reduced autocorrelation times compared to conventional classical proposals.
  arXiv  Detail & Related papers  (2025-02-28T07:31:38Z)
• Quantum Dynamical Hamiltonian Monte Carlo [0.0]
  A ubiquitous problem in machine learning is sampling from probability distributions that we only have access to via their log probability. We extend the well-known Hamiltonian Monte Carlo (HMC) method for Chain Monte Carlo (MCMC) sampling to leverage quantum computation in a hybrid manner.
  arXiv  Detail & Related papers  (2024-03-04T07:08:23Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Unbiasing time-dependent Variational Monte Carlo by projected quantum evolution [44.99833362998488]
  We analyze the accuracy and sample complexity of variational Monte Carlo approaches to simulate quantum systems classically. We prove that the most used scheme, the time-dependent Variational Monte Carlo (tVMC), is affected by a systematic statistical bias. We show that a different scheme based on the solution of an optimization problem at each time step is free from such problems.
  arXiv  Detail & Related papers  (2023-05-23T17:38:10Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Quantum-enhanced Markov chain Monte Carlo [0.22166578153935784]
  We introduce a quantum algorithm to sample from distributions that pose a bottleneck in several applications. 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. We find that this quantum algorithm converges in fewer iterations than common classical MCMC alternatives on relevant problem instances.
  arXiv  Detail & Related papers  (2022-03-23T15:50:12Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• Quantum Markov Chain Monte Carlo with Digital Dissipative Dynamics on Quantum Computers [52.77024349608834]
  We develop a digital quantum algorithm that simulates interaction with an environment using a small number of ancilla qubits. We evaluate the algorithm by simulating thermal states of the transverse Ising model.
  arXiv  Detail & Related papers  (2021-03-04T18:21:00Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Accelerating MCMC algorithms through Bayesian Deep Networks [7.054093620465401]
  Markov Chain Monte Carlo (MCMC) algorithms are commonly used for their versatility in sampling from complicated probability distributions. As the dimension of the distribution gets larger, the computational costs for a satisfactory exploration of the sampling space become challenging. We show an alternative way of performing adaptive MCMC, by using the outcome of Bayesian Neural Networks as the initial proposal for the Markov Chain.
  arXiv  Detail & Related papers  (2020-11-29T04:29:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.