Quantum Circuits for the Metropolis-Hastings Algorithm

• URL: http://arxiv.org/abs/2506.11576v2
• Date: Mon, 16 Jun 2025 14:16:48 GMT
• Title: Quantum Circuits for the Metropolis-Hastings Algorithm
• Authors: Baptiste Claudon, Pablo Rodenas-Ruiz, Jean-Philip Piquemal, Pierre Monmarché,
• 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 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 simulations.

Related papers

• 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)
• 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)
• 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)
• 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.