Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems

• URL: http://arxiv.org/abs/2604.20701v1
• Date: Wed, 22 Apr 2026 15:44:30 GMT
• Title: Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems
• Abstract summary: One approach known as quantum-enhanced Markov chain Monte Carlo uses quantum samples as a proposal distribution to accelerate convergence to a target distribution.<n>We propose a divide-and-conquer neural network surrogate framework for quantum sampling to accelerate MCMC under fixed Hamming weight constraints.<n>Our method consistently accelerated mixing as the system size increased, with average improvements in the autocorrelation decay rate constant by speedup factors of about $20.3$ and $7.6$ over classical pair-flip methods.
• Score: 2.9436347471485558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sampling problems are promising candidates for demonstrating quantum advantage, and one approach known as quantum-enhanced Markov chain Monte Carlo [Layden, D. et al., Nature 619, 282-287 (2023)] uses quantum samples as a proposal distribution to accelerate convergence to a target distribution. On the other hand, many practical problems are large-scale and constrained, making it difficult to construct efficient proposal distributions in classical methods and slowing down MCMC mixing. In this work, we propose a divide-and-conquer neural network surrogate framework for quantum sampling to accelerate MCMC under fixed Hamming weight constraints. Our method divides the interaction graph for an Ising problem into subgraphs, generates samples using QAOA for those subproblems with an XY mixer, and trains neural network surrogates conditioned on the Hamming weight to provide proposal distributions for each subset while preserving the constraint. In numerical experiments of Boltzmann sampling on 3-regular graphs, our method consistently accelerated mixing as the system size $N$ increased, with average improvements in the autocorrelation decay rate constant by speedup factors of about $20.3$ and $7.6$ over classical pair-flip methods based on nearest-neighbor and non-nearest-neighbor exchanges, respectively. We also applied the method to an MNIST feature mask optimization problem with $N=784$, obtaining faster energy convergence and a $2.03\%$ higher classification accuracy. These results show that our method enables efficient and scalable MCMC and can outperform classical methods for practical applications on NISQ devices.

Related papers

• Scalable Lindblad Noise Learning via Stochastic Tensor-Network Simulation [48.887627688666974]
  Learning dissipation rates in large-scale open quantum systems is a major obstacle for near-term quantum technologies.<n>Here, we propose a scalable noise-learning framework for Lindblad dissipation rates that combines a simulation method, the Jump Method (TJM)<n>We demonstrate the approach on two noise models in the Ising model, in which independent dissipation rates are learned for each site up to $N_mathrmsite=16$.<n>This combination of scalable numerics and rigorous theoretical guarantees positions TJM-based noise learning as a practical foundation for characterizing dissipation in large quantum devices.
  arXiv  Detail & Related papers  (2026-08-25T15:07:11Z)
• Precision Limits of Multiparameter Markovian-Noise Metrology [3.6347018475682087]
  We establish precision bounds for estimation of signals encoded through Markovian Lindblad dynamics.<n>Our bounds reveal Heisenberg-type scaling in the number of dissipative channels.<n>We show that, when the unknown parameters enter through the dissipative eigenrates, a Rapid Prepare-and-Measure protocol that tracks many distinct quantum jumps in parallel attains these limits.
  arXiv  Detail & Related papers  (2026-04-15T18:00:22Z)
• Fair sampling of ground-state configurations using hybrid quantum-classical MCMC algorithms [3.3083504598202733]
  We study the fair sampling properties of hybrid quantum-classical Markov chain Monte Carlo (MCMC) algorithms.<n>Using small Ising models, we show that MCMC post-processing corrects the sampling bias of quantum dynamics.<n>We also examine solution counting and find that the required number of transitions is comparable to that of WalkSAT.
  arXiv  Detail & Related papers  (2025-12-16T16:25:59Z)
• Better LMO-based Momentum Methods with Second-Order Information [48.580700968416444]
  Hessian-Corrected Momentum (HCM) aims to improve momentum convergence rates.<n>Hessian-Corrected Momentum can adapt to the geometry of the problem and achieve a faster rate than traditional momentum.<n>We extend the Linear Minimization Oracle framework by integrating HCM, and provide convergence guarantees under relaxed smoothness and arbitrary norm settings.
  arXiv  Detail & Related papers  (2025-12-15T11:43:09Z)
• Digitized Counterdiabatic Quantum Sampling [29.85893589594055]
  We propose a hybrid quantum-classical algorithm for efficient sampling from energy-based models, such as low-temperature Boltzmann distributions.<n>We show that classical sampling algorithms, including Metropolis-Hastings and the state-of-the-art low-temperature technique parallel tempering, require up to three orders of magnitude more samples to match the quality of DCQS.
  arXiv  Detail & Related papers  (2025-10-30T17:32:49Z)
• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Neural-network-assisted Monte Carlo sampling trained by Quantum Approximate Optimization Algorithm [0.8009842832476994]
  We propose a hybrid quantum-classical MCMC framework that combines a quantum circuit with a generative neural sampler (GNS)<n>GNS acts as a classical surrogate to efficiently emulate quantum outputs, thereby lifting circuit constraints.<n>These results establish the method as a viable sampling-based quantum algorithm for NISQ devices.
  arXiv  Detail & Related papers  (2025-06-02T05:26:26Z)
• Accelerating MCMC with Quantum Walks: Design, Implementation, and Results [3.004066195320147]
  We present the design and implementation of a novel MCMC algorithm based on the Discrete Quantum Walk (DQW) algorithm.<n>We demonstrate that it effectively captures the structure of the target distribution by leveraging quantum superposition.<n>In addition, we introduce a circuit extension that significantly improves convergence speed, which in turn enhances the scalability of the algorithm.
  arXiv  Detail & Related papers  (2025-04-16T13:53:32Z)
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines [0.0]
  We develop a tensor network (TN) based algorithm to reveal the low-energy spectrum of Ising spin-glass systems.<n>Our deterministic approach combines a branch-and-bound search strategy with an approximate calculation of marginals via TN contractions.<n>We benchmark our approach on random problems defined on Pegasus and Zephyr graphs with up to a few thousand spins.
  arXiv  Detail & Related papers  (2024-11-25T14:35:14Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)

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.