AI summaryⓘ
The authors investigate how to sample from small discrete Markov random fields (MRFs) using quantum methods that encode probabilities into quantum states. They find that classical methods like Gibbs sampling and parallel tempering perform surprisingly close to the quantum approach when measured by effective sample size, meaning the quantum speedup is less clear in practice. When including the classical preprocessing time, classical exact sampling is much faster than the quantum method. Additionally, the authors compare variational quantum circuits (VQCs) to classical matrix product states (MPS) for certain problem sizes and see that MPS achieves much higher accuracy. Overall, the study suggests that current classical techniques remain very competitive with quantum approaches for these small MRF sampling tasks.
Markov random fieldsQuantum samplingGibbs samplingParallel temperingEffective sample sizeInverse-CDF samplingAmplitude encodingVariational quantum circuitsMatrix product states
Abstract
Sampling from discrete Markov random fields (MRFs) is a hard problem. We study amplitude-encoded i.i.d. sampling for small MRFs where $2^n$ target probabilities are precomputed classically. This removes quantum exponential speedup but allows a clean comparison against classical MCMC based on independent circuit samples ($τ\approx 1$). Across 60 instances spanning five graph families (1k-step burn-in, 3k retained samples), the mean ESS ratios of Quantum to Single-Site Gibbs, Block Gibbs, Tuned-Block, and Parallel Tempering are $16.35$, $7.29$, $1.82$, and $1.79$, showing modern classical samplers substantially close this gap. Amortizing $O(2^n)$ preprocessing into wall-clock time, exact inverse-CDF sampling yields $17.7\text{M}$ ESS/s versus $488\text{K}$ ESS/s for the quantum sampler ($36\times$ mean rate, $153\times$ per-instance), confirming no wall-clock advantage. We characterize MCMC autocorrelation costs and benchmark amplitude-encoded state preparation at $n \in \{8,10,12\}$. An MPS scaling study ($n \le 40$) shows bond dimension $χ=32$ achieves $F=0.721\pm0.059$ at $n=40$. Finally, a matched-budget VQC vs. MPS comparison at $n \in \{8,10,12\}$ shows VQC fidelities fall far below MPS: $(F_{\mathrm{VQC}}, F_{\mathrm{MPS}}) = (0.31, 0.99), (0.21, 0.96), (0.17, 0.88)$ at compressions $10.7\times$, $34.1\times$, and $113.8\times$.