Quantum-enhanced Markov chain Monte Carlo

• URL: http://arxiv.org/abs/2203.12497v1
• Date: Wed, 23 Mar 2022 15:50:12 GMT
• Title: Quantum-enhanced Markov chain Monte Carlo
• Authors: David Layden, Guglielmo Mazzola, Ryan V. Mishmash, Mario Motta, Pawel Wocjan, Jin-Sung Kim, Sarah Sheldon
• Abstract summary: 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.
• Score: 0.22166578153935784
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Bounding speedup of quantum-enhanced Markov chain Monte Carlo [0.0]
  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  Detail & Related papers  (2024-03-05T16:20:01Z)
• 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)
• Accelerating variational quantum Monte Carlo using the variational quantum eigensolver [0.0]
  Variational Monte Carlo (VMC) methods are used to sample classically from distributions corresponding to quantum states. We propose replacing this initial distribution with samples produced using a quantum computer.
  arXiv  Detail & Related papers  (2023-07-15T05:45:55Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum-assisted Monte Carlo algorithms for fermions [5.625946422295428]
  We propose a family of scalable quantum-assisted Monte Carlo algorithms where the quantum computer is used at its minimal cost. We show that the hybrid Monte Carlo framework is a general way to suppress errors in the ground state obtained from classical algorithms.
  arXiv  Detail & Related papers  (2022-05-30T07:49:22Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• 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)
• Every Classical Sampling Circuit is a Quantum Sampling Circuit [0.8122270502556371]
  This note introduces "Q-marginals", which are quantum states encoding some probability distribution. It shows that these can be prepared directly from a classical circuit sampling for the probability distribution of interest.
  arXiv  Detail & Related papers  (2021-09-10T12:52:23Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor. We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
  arXiv  Detail & Related papers  (2021-01-21T22:18:49Z)
• Sampling Overhead Analysis of Quantum Error Mitigation: Uncoded vs. Coded Systems [69.33243249411113]
  We show that Pauli errors incur the lowest sampling overhead among a large class of realistic quantum channels. We conceive a scheme amalgamating QEM with quantum channel coding, and analyse its sampling overhead reduction compared to pure QEM.
  arXiv  Detail & Related papers  (2020-12-15T15:51:27Z)

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.