Quantum Circuits for the Metropolis-Hastings Algorithm

• URL: http://arxiv.org/abs/2506.11576v3
• Date: Fri, 22 Aug 2025 12:41:32 GMT
• Title: Quantum Circuits for the Metropolis-Hastings Algorithm
• Abstract summary: Quantum computers are expected to provide a speedup of Metropolis-Hastings (MH) simulations.<n>We present a quantum walk construction which follows the classical proposal-acceptance logic.<n>We expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Szegedy's quantization of a reversible Markov chain provides a quantum walk whose mixing time is quadratically smaller than that of the classical walk. Quantum computers are therefore expected to provide a speedup of Metropolis-Hastings (MH) simulations. Existing generic methods to implement the quantum walk require coherently computing the acceptance probabilities of the underlying Markov kernel. However, reversible computing methods require a number of qubits that scales with the complexity of the computation. This overhead is undesirable in near-term fault-tolerant quantum computing, where few logical qubits are available. In this work, we present a quantum walk construction which follows the classical proposal-acceptance logic, does not require further reversible computing methods, and uses a constant-sized ancilla register. Since each step of the quantum walk uses a constant number of proposition and acceptance steps, we expect the end-to-end quadratic speedup to hold for MH Markov Chain Monte-Carlo simulations.

Related papers

• Practical advantage beyond the quadratic speedup limit with fully-quantum walks [0.12891210250935145]
  We introduce a new class of fully-quantum walks in which both the proposal and acceptance steps are intrinsically quantum.<n>Under identical hardware assumptions, the resulting advantage runtime crossover is reduced from approximately $103$ years for conventional quantum walks to less than one day.
  arXiv  Detail & Related papers  (2026-07-24T18:00:06Z)
• Quantum Metropolis-Hastings via Penalised Qubitized Walks: Spectral Filtering and Circuit Implementation [0.45880283710344066]
  We construct and simulate an explicit circuit level implementation of a quantum Metropolis-Hastings algorithm based on the framework introduced by Claudon emphet al..<n>We present the full quantum workflow required to prepare a stationary distribution, including a number of modifications required to make the algorithm implementable in a realistic quantum circuit model.
  arXiv  Detail & Related papers  (2026-04-16T15:59:50Z)
• Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer [0.0]
  Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks.<n>We experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo algorithm on Quantinuum's H2 and Helios quantum computers.
  arXiv  Detail & Related papers  (2026-03-09T13:53:08Z)
• Optimising Iteration Scheduling for Full-State Vector Simulation of Quantum Circuits on FPGAs [1.221089353510972]
  We present a memory access pattern to optimise the number of iterations that need to be scheduled to execute a quantum gate.<n>We show that this approach results in a significant reduction in the time required to simulate a gate for each added control qubit.
  arXiv  Detail & Related papers  (2024-11-27T13:57:29Z)
• Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
  We present a model for parallelizing simulation of quantum circuit executions. The model can take advantage of its backend-agnostic features, enabling parallel quantum circuit execution over any target backend.
  arXiv  Detail & Related papers  (2024-06-05T17:16:07Z)
• Simulating Floquet scrambling circuits on trapped-ion quantum computers [0.6843496572893532]
  Information scrambling is one of the promising applications of quantum computing.<n>We demonstrate the Hayden-Preskill recovery protocol and the interferometric protocol for calculating out-of-time-ordered correlators.<n>Our experiments are made possible by extensively utilizing one of the highest-fidelity quantum processors currently available.
  arXiv  Detail & Related papers  (2024-05-13T10:22:17Z)
• The Cost of Emulating a Small Quantum Annealing Problem in the Circuit-Model [2.287415292857564]
  We show that the overhead of emulation is substantial even for a simple problem. This supports using analog quantum computation for solving time-dependent Hamiltonian dynamics in the short and mid-term.
  arXiv  Detail & Related papers  (2024-02-27T16:41:54Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Quantum Simulation of Dissipative Energy Transfer via Noisy Quantum Computer [0.40964539027092917]
  We propose a practical approach to simulate the dynamics of an open quantum system on a noisy computer. Our method leverages gate noises on the IBM-Q real device, enabling us to perform calculations using only two qubits. In the last, to deal with the increasing depth of quantum circuits when doing Trotter expansion, we introduced the transfer tensor method(TTM) to extend our short-term dynamics simulation.
  arXiv  Detail & Related papers  (2023-12-03T13:56:41Z)
• Sequential quantum simulation of spin chains with a single circuit QED device [5.841833052422423]
  Quantum simulation of many-body systems in materials science and chemistry are promising application areas for quantum computers. We show how a single-circuit quantum electrodynamics device can be used to simulate the ground state of a highly-entangled quantum many-body spin chain. We demonstrate that the large state space of the cavity can be used to replace multiple qubits in a qubit-only architecture, and could therefore simplify the design of quantum processors for materials simulation.
  arXiv  Detail & Related papers  (2023-08-30T18:00:03Z)
• 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 communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Fast-Forwarding with NISQ Processors without Feedback Loop [0.0]
  We present the Classical Quantum Fast Forwarding (CQFF) as an alternative diagonalisation based algorithm for quantum simulation. CQFF removes the need for a classical-quantum feedback loop and controlled multi-qubit unitaries. Our work provides a $104$ improvement over the previous record.
  arXiv  Detail & Related papers  (2021-04-05T14:29:33Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

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.