Divide-and-Conquer Neural Network Surrogates for Quantum Sampling: Accelerating Markov Chain Monte Carlo in Large-Scale Constrained Optimization Problems
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 , 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. , 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, 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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
-
Build two types of block partitioning, denoted as P(s) =lbrace B(s)1,. p. 3
.., B(s)M(s)r.Where the paper says it
1 and in Algorithm 1. (1) Build two types of block partitioning.
-
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.
-
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.
-
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 , 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
. , 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
. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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]. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
--- 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
-
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.
-
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.
-
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. -
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. -
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
- A Quantum Approximate Optimization Algorithm
- Classification with Quantum Neural Networks on Near Term Processors
- Quantum-Selected Configuration Interaction: classical diagonalization of Hamiltonians in subspaces selected by quantum computers
Related papers
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements
- Barriers to dequantization of near-term molecular electronic structure methods
- BRIDGE: Lazy-Move Compilation for Dual-Species Neutral-Atom Quantum Computers