Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer Preprint: APS/123-QED

Baptiste Claudon, Sergi Ramos-Calderer, Jean-Philip Piquemal · 2026

Read Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer Preprint: APS/123-QED by Baptiste Claudon, Sergi Ramos-Calderer, Jean-Philip Piquemal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-08395.txt.

Introduction

Claudon and colleagues realize the Markov Chain Monte Carlo method on a quantum machine in tests. Quantum methods cost greatly less than older ones for certain sampling tasks. QAE offers faster mean values of certain functions given access to the quantum state for that spread. Usually, samples often come from running a Markov chain. The authors use codes of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo routine on Quantinuum hardware. They operate straight on real qubits.

Catalog record

CREATORBaptiste Claudon, Sergi Ramos-Calderer, Jean-Philip Piquemal
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103742
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.08395

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer Preprint: APS/123-QED Baptiste Claudon, Sergi Ramos-Calderer, Jean-Philip Piquemal Abstract Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speedup the estimation of the mean of certain functions, given access to the quantum state corresponding to the probability distribution to be sampled from. Classically, samples are often obtained by running steps a Markov Chain. In this work, we experimentally use encodings of Markov chains to prepare quantum states and run a quantum Markov Chain Monte Carlo algorithm (qMCMC) on Quantinuum’s H2 and Helios quantum computers. We demonstrate that it is possible to obtain accurate results on current Noisy Intermediate Scale Quantum (NISQ) hardware, operating directly on the physical qubits. The pursuit of error corrected protocols has seen steady improvement on the quantum hardware. Contemporary quantum devices offer error rates at the point where complex subroutines are starting to be deployed with satisfactory results. While large scale error correction is distant, this early stage offers the opportunity to gauge the development of this technology by pushing the limits of the available hardware. Still, this necessitates a two-pronged approach to be successful. Intimate knowledge of both quantum device and middleware stack is essential to reach optimal performance of the quantum device. Moreover, breakthroughs at the algorithmic level reveal efficient protocols and decompositions that tighten the resources required from the machines in the first place. In this letter we focus on this interplay. We perform a thorough test of the required subroutines for the quantum Markov Chain Monte Carlo algorithm (qMCMC). Diverse encoding techniques are deployed and combined as per the recently proposed quantum encoding of the Metropolis Hastings algorithm 3 on ion trap quantum devices. Building on Grover’s work 4 , Brassard introduced the Quantum Amplitude Estimation algorithm 1 . Given access to quantum states encoding probability distributions, and a reversible algorithm to compute a function, the algorithm yields an estimate of its mean using quadratically fewer resources than the classical Monte Carlo method. Classically, samples from the distribution are often provided by implementing steps of a Markov Chain until the state’s distribution is close enough to its stationary measure. By analogy, it is possible to encode Markov Chains in unitary operations. Such encoding can be used to prepare the quantum state corresponding to the target stationary distribution, and therefore be used in Brassard’s Quantum Amplitude Estimation (QAE) method. In this work, we test several encodings of Markov chains on Quantinuum’s H2-1, H2-2 and Helios quantum computers 11 ; 9 ; 13 , focusing on two-state chains. First, we implement a Markov chain using the Linear Combination of Unitaries technique. The resulting encoding is used to sample from the stationary measure, and to estimate an expectation value using the quantum Metropolis–Hastings Markov Chain Monte Carlo (qMCMC) algorithm. Then, we use an encoding method proposed by Szegedy 16 to sample from the stationary distribution. Finally, we test two encoding methods that generalize well in the particular case of Metropolis-Hastings walks 5 ; 3 . The first is a modification of Szegedy’s method, the second is closer to Szegedy’s quantization method and encodes a process on the pairs of states. We use the first method to sample from the stationary distribution and verify that the corresponding quantum state is indeed an eigenvector of the second encoding method. I Quantum Markov Chain Monte Carlo Let \mathbb{S} be a finite state space of size n . A Markov kernel is a matrix P of positive numbers and size n\times n such that \sum_{y\in\mathbb{S}}P(x,y)=1 , for all x\in\mathbb{S} . Throughout this work, we restrict to ergodic Markov chains, admitting a unique stationary distribution \pi satisfying \pi P=\pi and \pi(x)>0 for all x\in\mathbb{S} . We denote the coherent encoding of a probability distribution \mu by \ket{\mu}=\sum_{x\in\mathbb{S}}\sqrt{\mu(x)}\ket{x} . In particular, \ket{\pi} denotes the stationary state. Ref. 8 provides a detailed exposition of the properties of such ergodic Markov kernels. Quantum algorithms for Markov chains rely on embedding non-unitary stochastic operators into larger unitary operators. We here give a precise definition of such encoding 15 . Definition 1 Let U be a unitary acting on a Hilbert space \mathcal{H} , and let \square:\mathbb{C}^{n}\to\mathcal{H} be a partial isometry. If U is symmetric, then (U,\square) is called a Symmetric Projected Unitary Encoding of an operator A if \square^{\dagger}U\square=A . These Symmetric Projected Unitary Encodings (SPUEs) naturally arise in quantum walk constructions. In practice, different implementations of \square and U correspond to different realizations of the same effective operator A . In this work we focus on experimentally comparing several such encodings. Given a SPUE, one can construct a quantum walk operator whose spectrum is directly related to that of the encoded symmetric operator. This can be stated more precisely as follows. Definition 2 Let (U,\square) be a SPUE of an operator A . Its associated qubitized walk operator is \mathcal{W}=(2\square\square^{\dagger}-1)U. (1) These SPUEs become the basis on which the quantum walk encoding is built from. The following theorem underlies all subsequent algorithms 16 ; 15 . Theorem 1 Let (U,\square) be a SPUE of an operator A , with qubitized walk operator \mathcal{W} . Let \lambda\in]-1,1[ be an eigenvalue of A with eigenvector \ket{v} . Define \theta=\cos^{-1}(\lambda) . Then \mathcal{W} has eigenvalues e^{\pm i\theta} with eigenvectors supported on the two-dimensional invariant subspace spanned by \square\ket{v} and U\square\ket{v} . If \lambda=\pm 1 , then \square\ket{v} is an eigenvector of \mathcal{W} with the same eigenvalue. From here, the qubitized walk operator follows. Given a Markov kernel P , define the quantum step operator \square=\sum_{x\in\mathbb{S}}\ket{x}\ket{P(x,\cdot)}\bra{x}. (2) For reversible chains with stationary distribution \pi , the discriminant matrix \mathcal{D}(x,y)=\sqrt{\frac{\pi(x)}{\pi(y)}}P(x,y) (3) is symmetric and shares the same spectrum as P . Using the SWAP operator S , the pair (S,\square) is a SPUE of \mathcal{D} . This is referred to as Szegedy’s quantization method 16 . The associated qubitized walk operator therefore encodes the spectral properties of the original Markov chain. Importantly, the stationary state \ket{\pi} satisfies \mathcal{D}\ket{\pi}=\ket{\pi} and corresponds to the unique 1 eigenstate of the walk operator in the range of \square . However, other partial isometries and unitary operators can also encode the discriminant matrix. Let \mathcal{W} denote the qubitized walk operator of a reversible ergodic chain. Since \square\ket{\pi} is the unique eigenvector of \mathcal{W} with eigenvalue 1 , it can be prepared using phase estimation 6 ; 10 . Recall that given an eigenvector \ket{\psi} of \mathcal{W} with eigenvalue e^{2\pi i\phi} , \phi\in\{k/2^{t}\}_{k=0}^{2^{t}-1} , the phase estimation of \mathcal{W} maps \ket{\psi}\ket{0} to \ket{\psi}\ket{2^{t}\phi} . Together with post-selection, the algorithm can also serve to prepare eigenstates. Ultimately, the target expectation value of the desired observable is extracted via amplitude estimation as follows. Let f:\mathbb{S}:\to[0,1] be an observable. The Monte Carlo algorithm aims at estimating \mathbb{E}_{\pi}(f)=\pi f=\sum_{x\in\mathbb{S}}\pi(x)f(x). (4) We assume access to f through a unitary O_{f} such that O_{f}\ket{x,0}=\sqrt{f(x)}\ket{x,0}+\sqrt{1-f(x)}\ket{x,1}. (5) Applied to \ket{\pi,0} , O_{f} yields the state \ket{\pi\cdot f}=\sum_{x\in\mathbb{S}}\sqrt{\pi(x)f(x)}\ket{x,0}+\sqrt{\pi(x)(1-f(x))}\ket{x,1}. (6) In particular, (2\ket{\pi\cdot f}\bra{\pi\cdot f}-1,\ket{0}) is a SPUE of the symmetric operator 2\braket{0|\pi\cdot f}\braket{\pi\cdot f|0}-1, (7) with eigenvalues -1 and 2\pi f-1 . Thus, applying the phase estimation algorithm to the qubitized walk operator of (2\ket{\pi\cdot

Read the complete text