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

arXiv:2604.20701 · quant-ph · Submitted 2026-04-22 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai.

Mira: And I'm Mira, here with Lev.

Kai: We're looking at the paper: "Divide-and-Conquer Neural Network Surrogates for Quantum Sampling".

Mira: Here's the gist of the paper. Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems proposes a divide-and-conquer neural network surrogate framework to accelerate Markov chain Monte Carlo (MCMC) sampling in large-scale constrained optimization problems by using quantum samples as proposal distributions conditioned on fixed Hamming weight constraints Problem Context and Motivation Sampling problems are promising candidates for demonstrating quantum advantage, and one approach known as quantum-enhanced Markov chain Monte Carlo

Layden, D. [Kai: et al., Nature 619, 282–287 (2023)] uses quantum samples as a proposal distribution to accelerate convergence to a target distribution 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 constrained problems, proposals must satisfy the constraints at all times, which restricts the structure of allowable transitions Under a fixed Hamming weight constraint, Kawasaki dynamics provide a proposal distribution that strictly satisfies the constraint by randomly selecting a pair of 0 and 1 and swapping them.

Mira: However, it has been pointed out that updates based on such pairflip dynamics may suffer from exponentially slow mixing with respect to the problem size To address this issue, we aim to construct a proposal distribution using samples generated from a quantum circuit, which can update more spins than pair-flip updates, while satisfying the constraint.

Kai: The proposed method focuses on large-scale Ising problems under a fixed Hamming weight constraint The core of the method involves four main steps summarized in Figure 1 and Algorithm 1 1.

Paper summary: Kai: To summarize this paper, the main thesis is that they propose a divide-and-conquer neural network surrogate framework to accelerate Markov chain Monte Carlo sampling when dealing with large scale constrained optimization problems.

Mira: They claim this is achieved by using quantum samples as proposal distributions that are specifically conditioned on fixed Hamming weight constraints to speed up convergence to the target distribution.

Lev: The problem they're addressing is that constructing efficient proposal distributions for these large, constrained problems classically is difficult, which slows down MCMC mixing significantly.

Kai: They propose building this by partitioning the system into blocks and running QAOA on each block using a Hamiltonian that only includes interactions within those blocks.

Mira: For each block, they train a conditional Masked Autoencoder neural network model conditioned on the Hamming weight of those samples to approximate the sample distribution from quantum circuits.

Lev: This surrogate distribution can then be used as the proposal distribution in MCMC, allowing efficient sampling without having to repeatedly execute full quantum circuits for every single proposal sample needed.

Kai: The key idea is that this approach allows for updates that satisfy the constraint while being more efficient than simple pair-flip dynamics, which is what Kawasaki dynamics provide.

Mira: They are applying this not only to low-temperature Boltzmann sampling but also to optimization problems that use MCMC as a subroutine, like simulated annealing, where it can lead to faster convergence to lower energy states.

Lev: The method is applicable because it addresses the issue of proposals needing to satisfy the constraints at all times in constrained problems, which severely restricts what transitions are allowed.

Kai: So the paper's core message is moving away from running expensive quantum circuits repeatedly toward using trained neural network surrogates derived from quantum samples to make MCMC more practical for large, constrained systems.

Mira: It matters because it shows a pathway to make MCMC sampling scalable and efficient for problems that are too big or too constrained for traditional classical methods alone.

Conclusion: Kai: So, the title points to a divide-and-conquer approach using neural network surrogates for quantum sampling to speed up MCMC sampling under fixed Hamming weight constraints.

Mira: It really suggests that we can get better performance in these hard optimization problems by leveraging quantum samples as smart proposals rather than relying on simple classical updates.

Lev: The implication is that we are moving towards a more practical way to use quantum-enhanced MCMC for large scale constrained problems on resource limited devices.

Kai: It means that this method could be useful not just for improving stationary mixing in sampling, but also as a divide-and-quer approach for fixed Hamming weight optimization itself.

Mira: In simpler terms, we can use quantum tools to sample smarter by using machine learning models trained on quantum data to navigate complex constraint spaces more effectively.

Graduate School of Engineering Science, The University of Osaka · Center for Quantum Information and Quantum Biology, The University of Osaka · RIKEN Center for Quantum Computing (RQC) · Graduate School of Informatics, Kyoto University

quant-ph

Submitted: 2026-04-22

Updated: 2026-11-10

Comments: 18 pages, 14 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 97/100

The gist: Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems proposes a divide-and-conquer neural network…

Key concepts

Quantum-enhanced MCMC
This technique uses samples generated from a quantum circuit as a proposal distribution to help the MCMC process converge faster to the desired target distribution. It leverages quantum sampling capabilities to overcome slow mixing issues inherent in classical sampling methods for complex problems.
Fixed Hamming Weight Constraint
This constraint requires that every configuration sampled must have exactly a specific number of '1's (or '0's) in its binary representation. This restriction limits the allowed moves during MCMC, making it challenging for classical proposals to explore the solution space efficiently.
Conditional MADE Neural Network
A Masked Autoencoder (MADE) is a neural network used here to model the proposal distribution. It is 'conditional' because its output depends on the Hamming weight of a specific block. This allows the model to learn how to propose next states that respect the required constraint for that particular segment of the problem.
Divide-and-Conquer Partitioning
The large optimization problem is broken down into smaller, manageable blocks. Instead of trying to propose moves for the entire system at once, this approach generates constrained proposals for each block separately. This parallel processing strategy makes constructing effective proposal distributions more feasible.

Terminology

Summary

Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems proposes a divide-and-conquer neural network surrogate framework to accelerate Markov chain Monte Carlo (MCMC) sampling in large-scale constrained optimization problems by using quantum samples as proposal distributions conditioned on fixed Hamming weight constraints

Problem Context and Motivation

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 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 constrained problems, proposals must satisfy the constraints at all times, which restricts the structure of allowable transitions Under a fixed Hamming weight constraint, Kawasaki dynamics provide a proposal distribution that strictly satisfies the constraint by randomly selecting a pair of 0 and 1 and swapping them. p. 0

Where the paper says it

, 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.

p. 0
Where the paper says it

, 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.

However, it has been pointed out that updates based on such pairflip dynamics may suffer from exponentially slow mixing with respect to the problem size To address this issue, we aim to construct a proposal distribution using samples generated from a quantum circuit, which can update more spins than pair-flip updates, while satisfying the constraint. p. 1
Where the paper says it

However, it has been pointed out that updates based on such pairflip dynamics may suffer from exponentially slow mixing with respect to the problem size, depending on the graph structure and the parameter regime [32]. To address this issue, we aim to construct a proposal distribution using samples generated from a quantum circuit, which can update more spins than pair-flip updates, while satisfying the constraint.

p. 1
Where the paper says it

However, it has been pointed out that updates based on such pairflip dynamics may suffer from exponentially slow mixing with respect to the problem size, depending on the graph structure and the parameter regime [32]. To address this issue, we aim to construct a proposal distribution using samples generated from a quantum circuit, which can update more spins than pair-flip updates, while satisfying the constraint.

Methodology Overview

The proposed method focuses on large-scale Ising problems under a fixed Hamming weight constraint The core of the method involves four main steps summarized in Figure 1 and Algorithm 1

  1. Build two types of block partitioning, denoted as P(s) =lbrace B(s)1,. p. 3

    Where the paper says it

    1 and in Algorithm 1. (1) Build two types of block partitioning.

    .., B(s)M(s)r.

  2. Run QAOA and sampling on each block using a Hamiltonian that includes only interactions within the block. p. 3

    Where the paper says it

    (2) Run QAOA and sampling on each block. We perform QAOA for each block using a Hamiltonian that includes only interactions within the block.

  3. Train conditional MADE neural network models for each block, conditioned on the Hamming weight. p. 4

    Where the paper says it

    (3) Train neural network models. We train a conditional MADE [35] for each block, using samples generated by a circuit optimized by QAOA with an XY mixer.

  4. Perform MCMC where a proposal is drawn from the corresponding MADE while preserving the Hamming weight. p. 1

    Where the paper says it

    During MCMC, a block is randomly selected, and a proposal is drawn from the corresponding MADE while preserving the Hamming weight, which ultimately serves as a proposal distribution for simultaneously updating multiple spins within the block. We perform numerical experiments to show that our method is effective.

Surrogate Model Training

The training signal is built by conditioning a Masked Autoencoder (MADE) on the Hamming weight of QAOA samples The conditional MADE defines an autoregressive proposal distribution over xB(s)m conditioned on kB(s)m, where kB(s)m is the block Hamming weight. The model is trained by maximum likelihood using QAOA block samples together with their block Hamming weights. p. 4

Where the paper says it

, it−1), and θ denotes the parameters of the neural network. We train the model by maximum likelihood using QAOA block samples {x (n) B (s) m } NB (s) m n=1 , where NB (s) m is the total number of samples on B (s) m , together with their block Hamming weights k (n) B (s) m := X i∈B (s) m x (n) B (s) m i , (27) namely, max θ NB (s) Xm n=1 log ˆq (B(s) m ) θ x (n) B (s) m | k (n) B (s) m .

p. 4
Where the paper says it

, it−1), and θ denotes the parameters of the neural network. We train the model by maximum likelihood using QAOA block samples {x (n) B (s) m } NB (s) m n=1 , where NB (s) m is the total number of samples on B (s) m , together with their block Hamming weights k (n) B (s) m := X i∈B (s) m x (n) B (s) m i , (27) namely, max θ NB (s) Xm n=1 log ˆq (B(s) m ) θ x (n) B (s) m | k (n) B (s) m .

This allows the model to mimic QAOA outputs conditioned on a desired Hamming weight. p. 4
Where the paper says it

During training, we feed the block Hamming weight of each QAOA sample together with the sample itself. At sampling time, by specifying a desired block Hamming weight, the model is expected to produce samples that mimic QAOA outputs conditioned on that Hamming weight.

p. 4
Where the paper says it

During training, we feed the block Hamming weight of each QAOA sample together with the sample itself. At sampling time, by specifying a desired block Hamming weight, the model is expected to produce samples that mimic QAOA outputs conditioned on that Hamming weight.

Performance and Results

Numerical experiments show that the method consistently accelerates mixing as the system size N increased, with average improvements in the autocorrelation decay rate 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. p. 0

Where the paper says it

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. 6 over classical pair-flip methods based on nearest-neighbor and non-nearest-neighbor exchanges, respectively.

The performance gap is maintained as the system size increases Furthermore, for the MNIST feature selection problem with N = 784 under a fixed Hamming weight constraint, our method achieves faster energy convergence and a 2. p. 1
Where the paper says it

By comparing the mixing speed, we show that our method outperforms both variants of Kawasaki dynamics once the QAOA size exceeds 6 qubits, and that the mixing performance continues to improve as the QAOA size increases. Next, as a more practical application, we consider feature selection on MNIST under a fixed Hamming weight constraint [29, 30].

03% higher classification accuracy compared to Kawasaki dynamics. p. 7
Where the paper says it

Compared with global Kawasaki, our proposed method reaches lower energy solutions in fewer steps. Table I reports the classification accuracy of logistic regression trained on the selected features.

Application in Feature Selection

In the application to MNIST feature selection, we solve a QUBO with N = 784 under the constraint to select pixels corresponding to important features. The method achieves faster energy convergence than Kawasaki dynamics and demonstrates better classification accuracy when MCMC is terminated after 50 steps. p. 1

Where the paper says it

Our method achieves faster energy convergence than Kawasaki dynamics. Furthermore, when MCMC is terminated after 50 steps, our method shows an improvement of about 2.

This suggests that the method is useful not only for improving stationary mixing in sampling but also as a divide-and-conquer approach for fixed Hamming weight optimization. p. 8
Where the paper says it

In contrast, when we stop at step 50, there is still a clear energy gap, and the proposed method achieves better accuracy, where the accuracy gap is 2. Overall, this experiment suggests that our method is useful not only for improving stationary mixing in sampling, but also as a divide-and-conquer approach for fixed Hamming weight optimization.

Conclusion

In conclusion, our method enables efficient and scalable MCMC for large-scale constrained optimization problems on resource-limited NISQ devices Our results show that the method outperforms classical methods in real applications even on resourcelimited NISQ devices. The framework successfully accelerates MCMC by using quantum samples as proposal distributions conditioned on fixed Hamming weight constraints. p. 0

Where the paper says it

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.

--- Page 1 ---

Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems proposes a divide-and-conquer neural network surrogate framework to accelerate Markov chain Monte Carlo (MCMC) sampling in large-scale constrained optimization problems by using quantum samples as proposal distributions conditioned on fixed Hamming weight constraints

Pruning redundant reasoning tokens

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 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 constrained problems, proposals must satisfy the constraints at all times, which restricts the structure of allowable transitions Under a fixed Hamming weight constraint, Kawasaki dynamics provide a proposal distribution that strictly satisfies the constraint by randomly selecting a pair of 0 and 1 and swapping them. However, it has been pointed out that updates based on such pairflip dynamics may suffer from exponentially slow mixing with respect to the problem size To address this issue, we aim to construct a proposal distribution using samples generated from a quantum circuit, which can update more spins than pair-flip updates, while satisfying the constraint.

How the training signal is built

The training signal is built by conditioning a Masked Autoencoder (MADE) on the Hamming weight of QAOA samples The conditional MADE defines an autoregressive proposal distribution over xB(s)m conditioned on kB(s)m, where kB(s)m is the block Hamming weight. The model is trained by maximum likelihood using QAOA block samples together with their block Hamming weights. This allows the model to mimic QAOA outputs conditioned on a desired Hamming weight.

Where the gains come from

The gains come from dividing the interaction graph into subgraphs (blocks) and generating constrained proposals for each block using QAOA samples conditioned on their respective Hamming weights Numerical experiments show that our method consistently accelerates mixing as the system size N increased, with average improvements in the autocorrelation decay rate 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 The performance gap is maintained as the system size increases

In conclusion, our method enables efficient and scalable MCMC for large-scale constrained optimization problems on resource-limited NISQ devices Our results show that the method outperforms classical methods in real applications even on resourcelimited NISQ devices The framework successfully accelerates MCMC by using quantum samples as proposal distributions conditioned on fixed Hamming weight constraints.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Divide-and-Conquer Neural Network Surrogate Framework for Quantum Sampling: This framework can be used to accelerate Markov chain Monte Carlo in large-scale constrained optimization problems by dividing the interaction graph into subgraphs and generating samples using QAOA with an XY mixer.

  2. Conditional MADE Training: The system can train a conditional MADE for each block, using the Hamming weight of the samples as a conditioning variable to provide proposal distributions for each subset while preserving the constraint.

  3. Constrained MCMC Proposal Generation: During MCMC, a proposal is drawn from the corresponding MADE conditioned on the block Hamming weight, ensuring that it preserves the Hamming weight and serves as a proposal distribution for simultaneously updating multiple spins within the block.

  4. Scalable Performance on Large Systems: The method consistently accelerates mixing as system size N increases, achieving speedup factors of about 20.3 and 7.6 over classical pair-flip methods on 3-regular graphs, demonstrating its effectiveness for large systems without sacrificing performance.

  5. Feature Selection Optimization: For feature selection on MNIST under a fixed Hamming weight constraint, the method achieves faster energy convergence and a 2.03% higher classification accuracy compared to classical Kawasaki dynamics when MCMC is terminated after 50 steps.

Abstract

Quantum-enhanced Markov chain Monte Carlo (MCMC) [D. Layden et al., Nature 619, 282--287 (2023)] is a promising way to use quantum-circuit samples as MCMC proposals to improve sampling efficiency. 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 14.0 and 7.7 over local and global Kawasaki dynamics, respectively. We also applied the method to an MNIST feature mask optimization problem with N=784, obtaining faster energy convergence and a classification accuracy 2.03 percentage points higher than that of global Kawasaki dynamics after 50 MCMC steps. These numerical results support the usefulness of surrogate proposals with a divide-and-conquer strategy for large-scale constrained sampling and finite-step optimization.

Sources

Related papers