# Techniques: Quantum-enhanced Markov Chain Monte Carlo for systems larger than your Quantum Computer

## What the paper contributes (one paragraph)

The Quantum-enhanced Markov Chain Monte Carlo (QeMCMC) of Layden et al. speeds up classical MCMC by generating the proposal step on a quantum computer, but it needs a QPU with as many qubits as there are spins in the problem. This paper introduces a coarse-graining framework, the Coarse Grained QeMCMC (CGQeMCMC), that runs the quantum proposal on a small subset (a "group") of the Ising lattice at each step, treating the remaining spins as an effective field, and iterating over disjoint groups so that arbitrary Hamming-distance moves are recovered. Using groups of size sqrt(n) (sqrt(n) groups of sqrt(n) spins), the authors show numerically, via spectral-gap analysis (up to 10 spins) and magnetization/energy convergence (up to 36 spins), that a scaling advantage over classical local and uniform proposals persists with only a quadratic-root number of simulated qubits. The method is hardware-adaptable, including to limited-connectivity QPUs, and composes with classical schemes such as parallel tempering.

## Techniques offered

- **Coarse-grained quantum-enhanced Markov chain Monte Carlo (CGQeMCMC)** - a coarse-graining framework that runs the QeMCMC quantum proposal step on small sqrt(n)-qubit subgroups of an Ising lattice, with non-selected spins folded into an effective field and disjoint groups sampled in succession, so a hard sampling problem of size n can be tackled on a QPU much smaller than n.
  - guarantee: produces a valid sampler (satisfies detailed balance, aperiodic and irreducible); the claimed scaling advantage (quantum enhancement factor between 1.84 and 2.6) is numerical evidence on a few Ising instances, not a proof.
  - quote: "This is done by Coarse Graining (CG) the problem instance - an Ising model lattice - in such a way that each subset ``group'' of the lattice can be evaluated in separate quantum computations, even on different QPUs in parallel."

## Where it could apply

- Target primitive(s): sampling (Markov Chain Monte Carlo, Metropolis-Hastings proposal); Trotterised Hamiltonian evolution (used to build the proposal); QAOA-style annealing Hamiltonian.
- Target application group(s): optimization, chemistry_materials, platforms_tooling.

## Caveats

The quantum part is run only in classical emulation, so all reported speedups are predicted/quantum-inspired rather than measured on hardware; the scaling claim rests on a small number of Ising instances (spectral gap limited to 10 spins) and the authors state it "cannot be explicitly proven by analysis of only a select few Ising model instances". Noise is not investigated, and the authors note that the one-shot nature of the algorithm makes standard error mitigation inapplicable. The supplied capability is a sampling method specialised to the Ising model; application beyond Ising is left to future work.