Substochastic Monte Carlo

Substochastic Monte Carlo is a diffusion Monte Carlo algorithm inspired by adiabatic quantum computation. It simulates the diffusion of a population of walkers in search space, while walkers are removed or duplicated based on how they perform according the cost function.

The initial set of walkers consists of random starting points (target_population = number of walkers), which are subjected to random transitions and a resampling process parameterized by alpha and beta:

• alpha: The probability of making a random transition (single variable change in the context of binary models)
• beta: The factor to apply when resampling the population (higher values for beta favor low-cost states more heavily)

Like Simulated Annealing or Population Annealing, the parameters alpha and beta are typically chosen in a time-dependent form, with alpha decreasing over time and beta increasing. This has the effect that the simulation focuses on exploration initially, and optimization later. Note that beta is not the same as inverse temperature in other annealing-based optimization methods, although it does govern roughly the same effect: when beta is small walkers are free to explore the space, but when beta gets large walkers in poor configurations are likely to be removed while those in good regimes will duplicate.

Features of Substochastic Monte Carlo on Azure Quantum

Substochastic Monte Carlo in Azure Quantum supports:

• Parameterized mode
• Ising and PUBO input formats
• CPU only

When to use Substochastic Monte Carlo

Substochastic Monte Carlo exhibits a tunneling-like property, akin to quantum adiabatic evolution, through the combination of diffusion and resampling. Hence it is likely to find best use in problems obtained from constrained optimization where the constraints cause severe nonconvexity that traps sequential methods such as Simulated Annealing or Tabu Search. If long runs of Simulated Annealing or Tabu Search are returning diverse values, then it is likely they are being trapped by a rough optimization landscape. In this case Substochastic Monte Carlo with a modest population size would be a good alternative to try.

Note

For further information on choosing which solver to use, please refer to this document.

Parameter-Free Substochastic Monte Carlo

Note

Parameter-Free Substochastic Monte Carlo is currently available to users in the Azure Quantum Early Access program. It will be available to all users in the near future.

Parameter-free Substochastic Monte Carlo searches for "optimal" parameters of the Substochastic Monte Carlo solver at runtime. This means that you do not need to set up parameters like alpha, beta, and so on. The only parameter required to run the parameter-free Substochastic Monte Carlo solver is timeout which represents the physical time in seconds that the solver is allowed to run.

Parameter Name	Default Value	Description
timeout (required)	5	Number of seconds to allow the solver to run.
seed (optional)	time based	Seed value - used for reproducing results.

Note that the timeout parameter is required to trigger the parameter-free Substochastic Monte Carlo solver. If you do not use the timeout parameter, the parameterized Substochastic Monte Carlo solver will be used instead, using the default parameters specified in the next section.

You can create the parameter-free solver by using code similar to the sample shown below:

from azure.quantum.optimization import SubstochasticMonteCarlo
# Requires a workspace already created.
solver = SubstochasticMonteCarlo(workspace, seed=48, timeout=10)

Parameterized Substochastic Monte Carlo

Suitable values for the target_population, step_limit and the resampling schedule depend on the problem and the magnitude (cost difference) of its variable changes.

• Modest target_population sizes (10-100) tend to work best. While some problems can benefit from larger populations, often one sees diminishing returns on effort to success.

• The beta_start, beta_stop range from Simulated Annealing can be a helpful guidance for the resampling parameter schedule.

• Substochastic Monte Carlo performs individual variable updates between resampling (rather than full sweeps). As a result the step_limit should be higher as compared to, e.g., Simulated Annealing.

Substochastic Monte Carlo supports the following parameters:

Parameter Name	Default Value	Description
step_limit	10000	Number of monte carlo steps. More steps will usually improve the solution (unless it is already at the global minimum).
target_population	number of threads	The number of walkers in the population (should be greater-equal 8).
alpha	linear 1..0	Schedule for the stepping chance (must be decreasing, i.e. alpha.initial > alpha.final).
beta	linear 0..5	Schedule for the resampling factor (must be increasing, i.e. beta.initial < beta.final).
seed (optional)	time based	Seed value - used for reproducing results.

To create a parameterized Substochastic Monte Carlo solver for the CPU using the SDK:

from azure.quantum.optimization import SubstochasticMonteCarlo
from azure.quantum.target.solvers import RangeSchedule
# Requires a workspace already created.
solver = SubstochasticMonteCarlo(workspace, step_limit=10000, target_population=64, beta=RangeSchedule("linear", 0, 5), seed=42)