Curator's Take
This research tackles a major bottleneck in quantum sampling by cleverly combining quantum algorithms with machine learning to handle real-world constrained optimization problems that are too large for current quantum computers to solve directly. The divide-and-conquer approach breaks complex problems into quantum-manageable subproblems, then uses neural networks to stitch the solutions together while preserving constraints - demonstrating over 20x speedup improvements in some cases. What makes this particularly exciting is the practical validation on an MNIST classification problem with 784 variables, showing that hybrid quantum-classical methods can already deliver meaningful advantages for machine learning tasks. This work represents an important step toward making quantum-enhanced sampling useful for large-scale optimization problems before we achieve full-scale fault-tolerant quantum computers.
— Mark Eatherly
Summary
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.