An End-to-End Hybrid Quantum-Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study
Abstract
Sampling from discrete Markov random fields (MRFs) is a hard problem. We study amplitude-encoded i.i.d. sampling for small MRFs where 2n target probabilities are precomputed classically. This removes quantum exponential speedup but allows a clean comparison against classical MCMC based on independent circuit samples (τ≈ 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(2n) preprocessing into wall-clock time, exact inverse-CDF sampling yields $17.7$M ESS/s versus $488$K ESS/s for the quantum sampler (36× mean rate, 153× per-instance), confirming no wall-clock advantage. We characterize MCMC autocorrelation costs and benchmark amplitude-encoded state preparation at n ∈ {8,10,12}. An MPS scaling study (n ≤ 40) shows bond dimension χ=32 achieves F=0.721±0.059 at n=40. Finally, a matched-budget VQC vs. MPS comparison at n ∈ {8,10,12} shows VQC fidelities fall far below MPS: (FVQC, FMPS) = (0.31, 0.99), (0.21, 0.96), (0.17, 0.88) at compressions 10.7×, 34.1×, and 113.8×.
Related
- Provable Quantum-Classical Separation for Continuous Gibbs Sampling
- A Topology-Aware Quantum-Classical Framework for Multi-Target Active Debris Removal using Gaussian Boson Sampling
- A Content-Addressed Workflow for Reproducible DANTE Gravitational-Wave Anomaly Analysis
- An Automated and Reproducible Workflow for Crack Identification and Damage Assessment of Fusion Materials
- Discrete classical electromagnetism
BibTeX
@misc{mazumder2026endtoend,
title = {{An End-to-End Hybrid Quantum-Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study}},
author = {Arul Rhik Mazumder and Elias Towe},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.09893},
eprint = {2607.09893},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.09893},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An End-to-End Hybrid Quantum-Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study
AU - Arul Rhik Mazumder
AU - Elias Towe
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2607.09893
UR - https://arxiv.org/abs/2607.09893
AB - 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 (τ≈ 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$M ESS/s versus $488$K ESS/s for the quantum sampler (36× mean rate, 153× per-instance), confirming no wall-clock advantage. We characterize MCMC autocorrelation costs and benchmark amplitude-encoded state preparation at n ∈ {8,10,12}. An MPS scaling study (n ≤ 40) shows bond dimension χ=32 achieves F=0.721±0.059 at n=40. Finally, a matched-budget VQC vs. MPS comparison at n ∈ {8,10,12} shows VQC fidelities fall far below MPS: (F_VQC, F_MPS) = (0.31, 0.99), (0.21, 0.96), (0.17, 0.88) at compressions 10.7×, 34.1×, and 113.8×.
ER -