Researchers at The University of Osaka and Kyoto University are addressing a critical challenge in quantum computing: accelerating Markov Chain Monte Carlo methods for complex optimization. Their work proposes a new “divide-and-conquer” framework using neural networks to simulate quantum sampling, achieving speedup factors of 20.3 and 7.6 over classical methods in Boltzmann sampling on 3-regular graphs as system size increases.

The team’s approach, designed for problems with fixed Hamming weight constraints, also improved classification accuracy by 2.03% when applied to an MNIST feature mask optimization problem with 784 variables, demonstrating efficient and scalable MCMC on near-term devices.

Neural Network Surrogates Accelerate Quantum Markov Chain Monte Carlo

The approach, detailed in recent work, partitions the interaction graph of an Ising problem into subgraphs, enabling sample generation using a Quantum Approximate Optimization Algorithm with an XY mixer. This division allows for the training of neural network surrogates, conditioned on the Hamming weight, to provide proposal distributions for each subset while maintaining the problem’s constraints. By dividing the problem into smaller, more manageable subgraphs, the researchers circumvent the difficulties of constructing efficient proposal distributions in classical methods, a common cause of slow mixing in Monte Carlo simulations.

The framework builds two types of block partitioning to achieve this, constructing vertex partitions to facilitate the process. This strategy contrasts with Kawasaki dynamics, and can reach meaningful results in fewer steps. The core innovation lies in the use of neural networks as surrogates for quantum sampling, a hybrid approach combining classical machine learning with the potential advantages of quantum computation.

Divide-and-Conquer Approach to Constrained Ising Problem Sampling

A 2.03% higher classification accuracy on an MNIST feature mask optimization problem was achieved by employing a novel approach to Markov Chain Monte Carlo sampling. This improvement stemmed from halting the computational process after 50 steps, a point where a clear energy gap existed between their method and conventional techniques, demonstrating a benefit beyond simply accelerating convergence to a stable state. The team’s framework tackles large-scale Ising problems with a fixed Hamming weight constraint by partitioning the problem’s interaction graph into discrete blocks.

The method’s design allows for updating more “spins”, a term referring to the quantum state of particles, than traditional pair-flip updates, a common technique in classical Monte Carlo methods. This capability is particularly valuable when dealing with constrained optimization problems where constructing efficient proposal distributions is a significant bottleneck.

The researchers specifically focused on 3-regular graphs, a type of network with a consistent number of connections per node, to test the framework’s scalability. Experiments on these 3-regular graphs revealed that the proposed method consistently accelerated mixing as the number of vertices, denoted as N, increased, a critical advantage for tackling complex systems. At step 3000, the energies achieved by this new method were comparable to those of classical approaches, suggesting similar overall performance once the system reaches a stable state.

However, the team’s approach demonstrated its strength in early stages of computation, achieving faster energy convergence and, consequently, improved classification accuracy. “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,” the researchers state in their published work. This suggests the technique offers a versatile solution for both accelerating sampling and tackling optimization challenges directly.

QAOA with XY Mixer Generates Subgraph Samples

The approach detailed uses a quantum circuit optimized by Quantum Approximate Optimization Algorithm, or QAOA, associated with smaller Ising problems defined on subgraphs of the larger system. Specifically, the team employed an XY mixer within the QAOA framework, a technique designed to preserve the Hamming weight of the quantum state throughout the computation. This preservation is critical because the method targets optimization problems with fixed Hamming weight constraints, ensuring the generated samples adhere to the problem’s inherent limitations.

The resulting sample distribution is intended to approximate a constrained, low-temperature Boltzmann distribution, a key element in Markov Chain Monte Carlo methods. To further refine the sampling process, conditional Masked Autoencoder for Distributions, or MADE, neural networks were trained for each subgraph. These networks use the Hamming weight of the samples as a conditioning variable, allowing them to generate surrogate distributions that closely mimic the low-temperature Boltzmann distribution at specific Hamming weights.

Autocorrelation Decay Improves by 20.3 and 7.6 with New Method

These gains were measured using the decay rate of autocorrelation based on Hamming distance, a metric for quantifying the convergence rate of the algorithm as system size increased. The research focused on 3-regular graphs, where the method consistently accelerated mixing even as the number of variables, N, rose to 512 while maintaining a fixed QAOA size of 16 qubits. The speedup stems from the method’s ability to update multiple spins simultaneously while adhering to fixed Hamming weight constraints, a feature that surpasses the limitations of pair-flip updates common in classical MCMC approaches.

By partitioning the interaction graph into QAOA blocks, the algorithm generates proposals that allow for larger-scale changes in the system’s state with each step. This is reflected in the decay rate, τ, where larger values indicate faster convergence. The simulations show a clear advantage for the new method across varying system and QAOA sizes.

Beyond simulations on 3-regular graphs, the method was also applied to a feature mask construction problem for MNIST digit recognition, yielding a 2.03% improvement in classification accuracy alongside faster energy convergence. This application involved an optimization problem with N = 784, demonstrating the method’s versatility beyond purely theoretical models.

The team investigated the relationship between system size and QAOA size, finding that the method consistently outperformed Kawasaki dynamics when the QAOA block size, |B|, was 6 or greater. The observed improvements in autocorrelation decay are quantified by comparing the ratios of τ values, highlighting the efficiency gains achieved through the proposed divide-and-conquer approach.

Fixed Hamming Weight Constraints and Kawasaki Dynamics Limitations

Constrained optimization problems often present a significant hurdle for Markov Chain Monte Carlo (MCMC) methods, as allowable transitions become increasingly restricted with larger system sizes. This limitation is particularly acute when dealing with fixed Hamming weight constraints, a condition appearing in areas like condensed matter physics and feature selection in machine learning. Traditional Kawasaki dynamics, employing pair-flip updates to satisfy these constraints, can suffer from exponentially slow mixing depending on the underlying graph structure and problem parameters.

The research demonstrates that a block-based approach to updating configurations offers a potential solution to this bottleneck. Rather than the typical pair-flip updates, the team implemented a method where a randomly selected block of spins is updated simultaneously using a proposal drawn from a conditional MADE network, all while preserving the fixed Hamming weight. This strategy aims to improve exploration of the solution space, a critical factor in efficient MCMC sampling.

Initial numerical experiments focused on constrained Boltzmann sampling on 3-regular graphs to assess the effectiveness of this new proposal distribution compared to Kawasaki dynamics. The performance advantage of this block-based method is not diminished as the system scales. Further investigation fixed the system size at N = 256 while varying the size of the QAOA circuit used to generate proposals, ranging from 2 to 16 qubits.

Results showed that the method consistently outperformed both variants of Kawasaki dynamics once the QAOA size exceeded 6 qubits, with continued improvements in mixing performance as the QAOA size increased. This suggests that the benefits of the approach are amplified with more sophisticated quantum-inspired proposal generation. Beyond simulations on idealized graphs, the team also applied their method to a practical problem: feature selection on the MNIST dataset under a fixed Hamming weight constraint.

The acceptance probability, defined as min(1, e^(-β_πE(y)-E(x))q(x)/q(y)), governs whether a proposed move to a new state is accepted during the MCMC process. Comparing the proposed method to baseline approaches, including random selection of 50 pixels and selection based on linear coefficients, the team found that their method, alongside Global Kawasaki dynamics, achieved higher accuracy. Specifically, the method demonstrated practical performance for feature selection, surpassing both Random 50 and Linear terms 50.

The evaluation included assessing accuracy at both step 50 and step 3000 of the MCMC run, providing insight into the convergence behavior of the algorithm. The team defined the feasible set as $Ω_{K}$ = x ∈ 0, $1^{N}$ | sum_(i = 1)^ $N x_{i}$ = K, representing all configurations satisfying the fixed Hamming weight constraint, and the target distribution as the Boltzmann distribution restricted to this set.

MNIST Feature Mask Optimization Demonstrates Enhanced Accuracy

The technique, which uses a “divide-and-conquer” framework, achieved this improvement on a problem involving 784 pixel features, constrained by a fixed Hamming weight. This performance gain highlights the method’s ability to not only accelerate sampling but also to enhance the quality of solutions in practical applications. After 50 steps, the proposed method achieved 79.51% accuracy, surpassing the 77.48% attained by Global Kawasaki dynamics. Extending the MCMC run to 3000 steps further solidified the advantage, with the proposed method reaching 80.51% accuracy, matching the performance of Global Kawasaki.

The approach divides the optimization problem into smaller subgraphs, generating samples using a Quantum Approximate Optimization Algorithm (QAOA) for each, and then employs neural network surrogates to create proposal distributions. This allows for the simultaneous update of multiple spins, a key factor in achieving faster mixing than traditional pair-flip updates.

The researchers also prepared an initial state biased towards a Hamming weight of two, using small-angle single-qubit rotation gates, to concentrate the optimization process around a specific neighborhood. These results show that the method enables efficient and scalable MCMC for large-scale constrained optimization problems, even on resource-limited near-term intermediate-scale quantum (NISQ) devices. By effectively combining quantum-inspired techniques with classical machine learning, the method offers a promising pathway towards tackling complex optimization challenges in various fields.

👉 More information
🗞 Divide-and-conquer neural-network surrogates for quantum sampling: Accelerating Markov-chain Monte Carlo in large-scale constrained optimization problems
✍️ Yuya Kawamata, Yuichiro Nakano and Keisuke Fujii
🧠 DOI: http://link.aps.org/doi/10.1103/qprn-rs96

More like this