Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2210.17526 · Communications Physics

Accelerated quantum Monte Carlo with probabilistic computers

Shuvro Chowdhury, Kerem Yunus Camsari, Supriyo Datta

Published Apr 27, 2023• 30 citations
arXivHTMLPDF

Abstract

Abstract Quantum Monte Carlo (QMC) techniques are widely used in a variety of scientific problems and much work has been dedicated to developing optimized algorithms that can accelerate QMC on standard processors (CPU). With the advent of various special purpose devices and domain specific hardware, it has become increasingly important to establish clear benchmarks of what improvements these technologies offer compared to existing technologies. In this paper, we demonstrate 2 to 3 orders of magnitude acceleration of a standard QMC algorithm using a specially designed digital processor, and a further 2 to 3 orders of magnitude by mapping it to a clockless analog processor. Our demonstration provides a roadmap for 5 to 6 orders of magnitude acceleration for a transverse field Ising model (TFIM) and could possibly be extended to other QMC models as well. The clockless analog hardware can be viewed as the classical counterpart of the quantum annealer and provides performance within a factor of < 10 of the latter. The convergence time for the clockless analog hardware scales with the number of qubits as ∼ N, improving the ∼ N2 scaling for CPU implementations, but appears worse than that reported for quantum annealers by D-Wave.

DOI
10.1038/s42005-023-01202-3

Related papers

Pushing the boundary of quantum advantage in hard combinatorial optimization with probabilistic computers

Shuvro Chowdhury, Navid Anjum Aadit, Andrea Grimaldi +12 more

Recent demonstrations on specialized benchmarks have reignited excitement for quantum computers, yet their advantage for real-world problems remains an open question. Here, we show that probabilistic computers, co-designed with hardware to implement Monte Carlo algorithms, provide a scalable classical pathway for solving hard optimization problems. We focus on two algorithms applied to three-dimensional spin glasses: discrete-time simulated quantum annealing and adaptive parallel tempering. We benchmark these methods against a leading quantum annealer. For simulated quantum annealing, increasing replicas improves residual energy scaling, consistent with extreme value theory. Adaptive parallel tempering, supported by non-local isoenergetic cluster moves, scales more favorably and outperforms simulated quantum annealing. Field Programmable Gate Arrays or specialized chips can implement these algorithms in modern hardware, leveraging massive parallelism to accelerate them while improving energy efficiency. Our results establish a rigorous classical baseline for assessing practical quantum advantage and present probabilistic computers as a scalable platform for real-world optimization challenges.

arXiv:2503.10302•Nature Communications•Oct 16, 2025•10 citations

A fidelity metric for quantum annealing benchmarked by extreme scaling quantum Monte-Carlo simulations

Gabriel Gouraud, Miha Srdinsek, Xavier Waintal

Quantum annealers are supposed to follow adiabatically the ground state of a system as its Hamiltonian slowly interpolates between a trivial phase and a non-trivial one; the non-trivial ground state being the solution to an optimization problem. Overwhelmingly, their performances are measured in terms of how well or fast the optimization problem is solved. While pragmatic, this approach is inherently brittle as it strongly depends on the problem considered and the classical algorithm used as the reference benchmark. Here, we propose a quantity that not only measures the end result but also the quality of the actual quantum annealing process itself. Our metric is the quantum annealing counterpart of the fidelity-per gate of gate-based quantum computers. It takes the form of an accuracy $ε$ for the equation of state of the annealer. We calculate benchmark values of $ε$ using two variants of the simulated quantum annealing technique for Rydberg atoms systems. Our first approach uses variational quantum Monte-Carlo with an ansatz inspired by thermal annealing. It suggests that within $ε\sim 10^{-2}-10^{-3}$, a quantum annealer is indistinguishable from its thermal classical counterpart. Critically, we could reach this precision up to $100,000,000$ atoms on a single CPU. Our second approach (based on Green function quantum Monte-Carlo) reaches accuracies around $ε\sim 10^{-4}$ and we have run it up to $100,000$ atoms. These results outperform current Rydberg atom quantum annealing experimental platforms in both precision and size by orders of magnitude and put severe constraints for future hardware.

quant-pharXiv:2606.26233•Jun 26, 2026•0 citations

Partition Function Estimation Using Analog Quantum Processors

Thinh Le, Elijah Pelofske

We evaluate using programmable superconducting flux qubit D-Wave quantum annealers to approximate the partition function of Ising models. We propose the use of two distinct quantum annealer sampling methods: chains of Monte Carlo-like reverse quantum anneals, and standard linear-ramp quantum annealing. The control parameters used to attenuate the quality of the simulations are the effective analog energy scale of the J coupling, the total annealing time, and for the case of reverse annealing the anneal-pause. The core estimation technique is to sample across the energy spectrum of the classical Hamiltonian of interest, and therefore obtain a density of states estimate for each energy level, which in turn can be used to compute an estimate of the partition function with some sampling error. This estimation technique is powerful because once the distribution is sampled it allows thermodynamic quantity computation at arbitrary temperatures. On a $25$ spin $\pm J$ hardware graph native Ising model we find parameter regimes of the D-Wave processors that provide comparable result quality to two standard classical Monte Carlo methods, Multiple Histogram Reweighting and Wang-Landau. Remarkably, we find that fast quench-like anneals can quickly generate ensemble distributions that are very good estimates of the true partition function of the classical Ising model; on a Pegasus graph-structured QPU we report a logarithmic relative error of $7.6 \times 10^{-6}$, from $171,000$ samples generated using $0.2$ seconds of QPU time with an anneal time of $8$ nanoseconds per sample which is interestingly within the closed system dynamics timescale of the superconducting qubits.

quant-pharXiv:2512.19685•Dec 23, 2025•0 citations

Quantum Annealing with Markov Chain Monte Carlo Simulations and D-Wave Quantum Computers

Yazhen Wang, Shang Wu, Jian Zou

Quantum computation performs calculations by using quantum devices instead of electronic devices following classical physics and used by classical computers. Although general purpose quantum computers of practical scale may be many years away, special purpose quantum computers are being built with capabilities exceeding classical computers. One prominent case is the so-called D-Wave quantum computer, which is a computing hardware device built to implement quantum annealing for solving combinatorial optimization problems. Whether D-Wave computing hardware devices display a quantum behavior or can be described by a classical model has attracted tremendous attention, and it remains controversial to determine whether quantum or classical effects play a crucial role in exhibiting the computational input–output behaviors of the D-Wave devices. This paper consists of two parts where the first part provides a review of quantum annealing and its implementations, and the second part proposes statistical methodologies to analyze data generated from annealing experiments. Specifically, we introduce quantum annealing to solve optimization problems and describe D-Wave computing devices to implement quantum annealing. We illustrate implementations of quantum annealing using Markov chain Monte Carlo (MCMC) simulations carried out by classical computers. Computing experiments have been conducted to generate data and compare quantum annealing with classical annealing. We propose statistical methodologies to analyze computing experimental data from a D-Wave device and simulated data from the MCMC based annealing methods, and establish asymptotic theory and check finite sample performances for the proposed statistical methodologies. Our findings confirm bimodal histogram patterns displayed in input–output data from the D-Wave device and both U-shape and unimodal histogram patterns exhibited in input–output data from the MCMC based annealing methods. Further statistical explorations reveal possible sources for the U-shape patterns. On the other hand, our statistical analysis produces statistical evidence to indicate that input–output data from the D-Wave device are not consistent with the stochastic behaviors of any MCMC based annealing models under the study. We present a list of statistical research topics for the future study on quantum annealing and MCMC simulations.

Statistical Science•Aug 1, 2016•24 citations

Exponential challenges in unbiasing quantum Monte Carlo algorithms with quantum computers

Guglielmo Mazzola, Giuseppe Carleo

Recently, Huggins et. al. [Nature, 603, 416-420 (2022)] devised a general projective Quantum Monte Carlo method suitable for implementation on quantum computers. This hybrid approach, however, relies on a subroutine -the computation of the local energy estimator on the quantum computer -that is intrinsically affected by an exponential scaling of the computational time with the number of qubits. By means of numerical experiments, we show that this exponential scaling manifests prominently already on systems below the point of "quantum advantage". For the prototypical transverse-field Ising model, we show that the required time resources to compete with classical simulations on around 40 qubits are already of the order of $10^{13}$ projective measurements, with an estimated running time of a few thousand years on superconducting hardware. These observations strongly suggest that the proposed hybrid method, in its present form, is unlikely to offer a sizeable advantage over conventional quantum Monte Carlo approaches.

arXiv:2205.09203•May 18, 2022•8 citations

Experimental Realization of the Markov Chain Monte Carlo Algorithm on a Quantum Computer

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

Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up 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 simulating 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 (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.

quant-pharXiv:2603.08395•Mar 10, 2026•0 citations
Abstract Quantum Monte Carlo (QMC) techniques are widely used in a variety of scientific problems and much work has been dedicated to developing optimized algorithms that can accelerate QMC on standard processors (CPU). With the advent of various special purpose devices and domain specific hardware, it has become increasingly important to establish clear benchmarks of what improvements these technologies offer compared to existing technologies. In this paper, we demonstrate 2 to 3 orders of magnitude acceleration of a standard QMC algorithm using a specially designed digital processor, and a further 2 to 3 orders of magnitude by mapping it to a clockless analog processor. Our demonstration provides a roadmap for 5 to 6 orders of magnitude acceleration for a transverse field Ising model (TFIM) and could possibly be extended to other QMC models as well. The clockless analog hardware can be viewed as the classical counterpart of the quantum annealer and provides performance within a factor of < 10 of the latter. The convergence time for the clockless analog hardware scales with the number of qubits as ∼ N, improving the ∼ N2 scaling for CPU implementations, but appears worse than that reported for quantum annealers by D-Wave.
Recent demonstrations on specialized benchmarks have reignited excitement for quantum computers, yet their advantage for real-world problems remains an open question. Here, we show that probabilistic computers, co-designed with hardware to implement Monte Carlo algorithms, provide a scalable classical pathway for solving hard optimization problems. We focus on two algorithms applied to three-dimensional spin glasses: discrete-time simulated quantum annealing and adaptive parallel tempering. We benchmark these methods against a leading quantum annealer. For simulated quantum annealing, increasing replicas improves residual energy scaling, consistent with extreme value theory. Adaptive parallel tempering, supported by non-local isoenergetic cluster moves, scales more favorably and outperforms simulated quantum annealing. Field Programmable Gate Arrays or specialized chips can implement these algorithms in modern hardware, leveraging massive parallelism to accelerate them while improving energy efficiency. Our results establish a rigorous classical baseline for assessing practical quantum advantage and present probabilistic computers as a scalable platform for real-world optimization challenges.
Quantum annealers are supposed to follow adiabatically the ground state of a system as its Hamiltonian slowly interpolates between a trivial phase and a non-trivial one; the non-trivial ground state being the solution to an optimization problem. Overwhelmingly, their performances are measured in terms of how well or fast the optimization problem is solved. While pragmatic, this approach is inherently brittle as it strongly depends on the problem considered and the classical algorithm used as the reference benchmark. Here, we propose a quantity that not only measures the end result but also the quality of the actual quantum annealing process itself. Our metric is the quantum annealing counterpart of the fidelity-per gate of gate-based quantum computers. It takes the form of an accuracy εεε for the equation of state of the annealer. We calculate benchmark values of εεε using two variants of the simulated quantum annealing technique for Rydberg atoms systems. Our first approach uses variational quantum Monte-Carlo with an ansatz inspired by thermal annealing. It suggests that within ε∼10−2−10−3ε\sim 10^{-2}-10^{-3}ε∼10−2−10−3, a quantum annealer is indistinguishable from its thermal classical counterpart. Critically, we could reach this precision up to 100,000,000100,000,000100,000,000 atoms on a single CPU. Our second approach (based on Green function quantum Monte-Carlo) reaches accuracies around ε∼10−4ε\sim 10^{-4}ε∼10−4 and we have run it up to 100,000100,000100,000 atoms. These results outperform current Rydberg atom quantum annealing experimental platforms in both precision and size by orders of magnitude and put severe constraints for future hardware.
We evaluate using programmable superconducting flux qubit D-Wave quantum annealers to approximate the partition function of Ising models. We propose the use of two distinct quantum annealer sampling methods: chains of Monte Carlo-like reverse quantum anneals, and standard linear-ramp quantum annealing. The control parameters used to attenuate the quality of the simulations are the effective analog energy scale of the J coupling, the total annealing time, and for the case of reverse annealing the anneal-pause. The core estimation technique is to sample across the energy spectrum of the classical Hamiltonian of interest, and therefore obtain a density of states estimate for each energy level, which in turn can be used to compute an estimate of the partition function with some sampling error. This estimation technique is powerful because once the distribution is sampled it allows thermodynamic quantity computation at arbitrary temperatures. On a 252525 spin ±J\pm J±J hardware graph native Ising model we find parameter regimes of the D-Wave processors that provide comparable result quality to two standard classical Monte Carlo methods, Multiple Histogram Reweighting and Wang-Landau. Remarkably, we find that fast quench-like anneals can quickly generate ensemble distributions that are very good estimates of the true partition function of the classical Ising model; on a Pegasus graph-structured QPU we report a logarithmic relative error of 7.6×10−67.6 \times 10^{-6}7.6×10−6, from 171,000171,000171,000 samples generated using 0.20.20.2 seconds of QPU time with an anneal time of 888 nanoseconds per sample which is interestingly within the closed system dynamics timescale of the superconducting qubits.
Quantum computation performs calculations by using quantum devices instead of electronic devices following classical physics and used by classical computers. Although general purpose quantum computers of practical scale may be many years away, special purpose quantum computers are being built with capabilities exceeding classical computers. One prominent case is the so-called D-Wave quantum computer, which is a computing hardware device built to implement quantum annealing for solving combinatorial optimization problems. Whether D-Wave computing hardware devices display a quantum behavior or can be described by a classical model has attracted tremendous attention, and it remains controversial to determine whether quantum or classical effects play a crucial role in exhibiting the computational input–output behaviors of the D-Wave devices. This paper consists of two parts where the first part provides a review of quantum annealing and its implementations, and the second part proposes statistical methodologies to analyze data generated from annealing experiments. Specifically, we introduce quantum annealing to solve optimization problems and describe D-Wave computing devices to implement quantum annealing. We illustrate implementations of quantum annealing using Markov chain Monte Carlo (MCMC) simulations carried out by classical computers. Computing experiments have been conducted to generate data and compare quantum annealing with classical annealing. We propose statistical methodologies to analyze computing experimental data from a D-Wave device and simulated data from the MCMC based annealing methods, and establish asymptotic theory and check finite sample performances for the proposed statistical methodologies. Our findings confirm bimodal histogram patterns displayed in input–output data from the D-Wave device and both U-shape and unimodal histogram patterns exhibited in input–output data from the MCMC based annealing methods. Further statistical explorations reveal possible sources for the U-shape patterns. On the other hand, our statistical analysis produces statistical evidence to indicate that input–output data from the D-Wave device are not consistent with the stochastic behaviors of any MCMC based annealing models under the study. We present a list of statistical research topics for the future study on quantum annealing and MCMC simulations.
Recently, Huggins et. al. [Nature, 603, 416-420 (2022)] devised a general projective Quantum Monte Carlo method suitable for implementation on quantum computers. This hybrid approach, however, relies on a subroutine -the computation of the local energy estimator on the quantum computer -that is intrinsically affected by an exponential scaling of the computational time with the number of qubits. By means of numerical experiments, we show that this exponential scaling manifests prominently already on systems below the point of "quantum advantage". For the prototypical transverse-field Ising model, we show that the required time resources to compete with classical simulations on around 40 qubits are already of the order of 101310^{13}1013 projective measurements, with an estimated running time of a few thousand years on superconducting hardware. These observations strongly suggest that the proposed hybrid method, in its present form, is unlikely to offer a sizeable advantage over conventional quantum Monte Carlo approaches.
Quantum algorithms present a quadratically improved complexity over classical ones for certain sampling tasks. For instance, the Quantum Amplitude Estimation (QAE) algorithm promises to speed up 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 simulating 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 (qMCMC) algorithm on Quantinuum System Model H2 and Quantinuum Helios quantum computers. We first demonstrate that it is possible to obtain accurate results by operating directly on the physical qubits. Crucially, to pave the way toward fault-tolerant execution, we also implement these algorithms using logical qubits protected by the Iceberg Quantum Error Detection (QED) code. By applying multiple rounds of mid-circuit QED during a random walk, we successfully catch and filter out hardware errors. These experiments demonstrate the feasibility of qMCMC on quantum hardware, bringing us closer to realizing quadratic quantum speedups with broad applications ranging from molecular modeling to machine learning and finance.