An End-to-End Hybrid Quantum--Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study

• URL: http://arxiv.org/abs/2607.09893v1
• Date: Fri, 10 Jul 2026 18:33:14 GMT
• Title: An End-to-End Hybrid Quantum--Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study
• Abstract summary: We study amplitude-encoded i.i.d. sampling for small discrete Markov random fields (MRFs)<n>This removes quantum exponential speedup but allows a clean comparison against classical MCMC based on independent circuit samples.<n>A matched-budget VQC vs. MPS comparison shows VQC fidelities fall far below MPS: $(F_mathrmVQC, F_mathrmMPS) = (0.31, 0.96), (0.21, 0.96), (0.17, 0.88)$ at compressions $10.7times$, $34.1times$, and $11
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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$.

Related papers

• M-QAM MIMO Maximum-Likelihood Detection with QAOA: ML-Rate Offline Angle Design and Correlated Infinite-Size Spin-Glass Models [9.13755431537592]
  The quantum approximate optimization algorithm (QAOA) targets NP-hard maximum-likelihood (ML) detection in multiple-input multiple-output (MIMO) systems.<n>Tests reach 4096-QAM, 128 antennas, $p=30$ and per-symbol SNR 0-45 dB.<n>The approach points toward near-optimum decoding on deeper noiseless fault-tolerant quantum (FTQ) circuits.
  arXiv  Detail & Related papers  (2026-08-18T12:45:47Z)
• Pruning Deep Neural Networks via the Marchenko--Pastur Distribution [0.0]
  We study a Marchenko--Pastur (MP) random-matrix approach to pruning deep neural networks with very small post-pruning fine-tuning budgets.<n>The main practical contribution is accuracy retention under short calibration and fine-tuning schedules.
  arXiv  Detail & Related papers  (2026-05-23T19:44:02Z)
• Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence [0.0]
  We present QKLA (Quantum Kullback-Leibler Amplitude estimation), a quantum algorithm that encodes a clipped logdensity ratio as amplitude estimation to recover a clipped KL expectation.<n>QKLA achieves a quadratic precision improvement, needing only $mathcalO((L/)log (1/)$ queries, where $L$ is the log-ratio clip bound.<n>Under per-stratum conditional-oracle access and a margin assumption for CI decisions, embedding this estimator in the PC algorithm compounds to an $widetilde (1/(L
  arXiv  Detail & Related papers  (2026-04-25T21:46:28Z)
• Hardware Validation of DAGI via a Modular "Ridge" Signature and High-Order Synergistic Information [0.0]
  DAGI (Directed Acyclic Graph Information) framework on IBM Quantum hardware.<n>Small, controlled experiment whose ideal output distribution is constrained to a low-dimensional modular manifold (a "ridge)<n>Key recovery exceeds chance: per-shot accuracy 0.1689 (chance 0.125, 95% Wilson CI [0.1610, 0.1772])<n>These results support the claim that DAGI detects and quantifies non-trivial, hardware-resilient information structure.
  arXiv  Detail & Related papers  (2026-04-16T14:16:59Z)
• qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices [3.4129039170001314]
  Clustering on NISQ hardware is constrained by data loading and limited qubits.<n>We present qc-kmeans, a hybrid $k$-means that summarizes a dataset with a constant-size Fourier-feature sketch and selects centroids by solving small per-group QUBOs with shallow QAOA circuits.
  arXiv  Detail & Related papers  (2025-10-26T05:44:17Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Scalable Spike-and-Slab [19.548599544810937]
  Spike-and-slab priors are commonly used for Bayesian variable selection. Existing samplers for spike-and-slab posteriors incur prohibitive computational costs when the number of variables is large.
  arXiv  Detail & Related papers  (2022-04-04T17:28:48Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  We are given i.i.d. samples from a distribution of the form $Z = (1-epsilon) X + epsilon B$, where $X$ is a zero-mean and unknown covariance Gaussian $mathcalN(0, Sigma)$. In the absence of contamination, prior work gave a simple tester for this hypothesis testing task that uses $O(d)$ samples. We prove a sample complexity lower bound of $Omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma
  arXiv  Detail & Related papers  (2020-12-31T18:24:41Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30:48Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.