New Solvers Further Enhance the Microsoft Azure Quantum Optimization Offering

(HPCWire) Microsoft Quantum chose to build one of the most comprehensive cloud offerings for binary optimization covering both their Azure Quantum optimization offering and a diverse set of offerings from their partners. These include 1QBit 1Qloud as well as Toshiba’s Simulated Bifurcation Machine.
Microsoft announced that its Azure Quantum is expanding its solver offering even further. In addition to existing solvers (including Parallel Tempering and Quantum Monte Carlo), users now have access to two additional algorithms:
Substochastic Monte Carlo (SSMC)

Population Annealing (PA)
Both are population algorithms. They borrow from years of research in physics and quantum mechanics and are inspired by natural processes. Optimization problems arise across different industries from applications in supply chain management and workforce scheduling to portfolio management.
Binary optimization allows you to express an optimization problem definition in code and use heuristics to find a set of good solutions. Our new solvers join a family of optimization offerings that are available in Azure Quantum today.

How do these new solvers work?
Substochastic Monte Carlo (SSMC) is a process designed to emulate the tunneling effect exploited by quantum annealing. When running the algorithm, Microsoft deploys a collection of walkers (the population) across the problem landscape. Like in Simulated Annealing (SA), they explore the space and try to find minima.
At each iteration of the algorithm, each walker has the option to hop to a new location, stay where it is, add new walkers at its current location, or remove itself from the population. Parameters in the algorithm govern the probability of these actions, but each walker can only perform one of them at each iteration.
Usually, the parameters are chosen in such a way that early in the run walkers are more likely to hop around. This encourages wide exploration of the problem space to find potential minima. Over time the addition and removal process starts to dominate.
Walkers with a relatively unfavorable objective value are more likely to be removed from the population, while those with better values are more likely to spawn more walkers nearby. This process encourages good exploration of local minima.
SSMC has proven itself to be highly successful when applied to MAX-SAT problems.
Population Annealing (PA) tries to find good solutions by creating an ensemble of parallel runs of SA. Each replica in the ensemble takes several SA steps at a fixed temperature, which can be done in parallel. However, before proceeding to the next temperature in the annealing schedule, we first “resample” the whole ensemble. This means that replicas are copied or removed with a probability dependent on their energies—better (lower) energy replicas are more likely to be copied, and ones with worse (higher) energies are more likely to be removed from the ensemble.
This helps ensure more promising replicas the chance to thoroughly explore the local landscape while also allowing a smaller number of worse-performing replicas to exist in case they happen upon unexpected and unexplored minima.