June 22, 2021 — There is no one algorithm that fits every optimization problem. Having a full portfolio at your fingertips is important when tuning optimization solutions for the best outcome and the highest impact.

That is why Microsoft Quantum chose to build one of the most comprehensive cloud offerings for binary optimization covering both our Azure Quantum optimization offering and a diverse set of offerings from our partners. These include 1QBit 1Qloud as well as Toshiba’s Simulated Bifurcation Machine.

We are excited to share that Azure Quantum is expanding its solver offering even further. In addition to our existing solvers (including Parallel Tempering and Quantum Monte Carlo) you 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. We can’t wait for you to try them yourself.

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, we deploy 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 us ensure that we give 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.

PA lends itself to large, rugged problem spaces and can yield higher quality results than SA.

Tap into one of the most comprehensive optimization offerings today
Get started with optimization in Azure Quantum today with our quick start resources for Microsoft QIO.

Learn more about how the Azure Quantum team works with customers and partners to solve some of the world’s most complex computational challenges.

---

Source: Krysta Svore, Microsoft Quantum