Computing inverse temperature upper and lower bounds

A method for use with a computing device, the method comprising:

• receiving an energy function of a combinatorial optimization problem to which a solution is configured to be estimated over a plurality of timesteps;
• computing an inverse temperature lower bound for the combinatorial optimization problem, wherein computing the inverse temperature lower bound includes estimating a maximum change in the energy function between successive timesteps of the plurality of timesteps;
• computing an inverse temperature upper bound for the combinatorial optimization problem, wherein computing the inverse temperature upper bound includes estimating a minimum change in the energy function between successive timesteps of the plurality of timesteps;
• computing the solution to the combinatorial optimization problem at least in part by executing a Markov chain Monte Carlo (MCMC) algorithm over the plurality of timesteps, wherein:
• an inverse temperature of the MCMC algorithm is set to the inverse temperature lower bound during an initial timestep of the plurality of timesteps;
• and
• the inverse temperature of the MCMC algorithm is set to the inverse temperature upper bound during a final timestep of the plurality of timesteps;
• and
• outputting the solution.

A computing device comprising:

• a processor configured to:
• receive an energy function of a combinatorial optimization problem to which a solution is configured to be estimated over a plurality of timesteps;
• compute an inverse temperature lower bound for the combinatorial optimization problem, wherein computing the inverse temperature lower bound includes estimating a maximum change in the energy function between successive timesteps of the plurality of timesteps at least in part by computing, over a plurality of variables of the energy function, a maximum of:
• a sum of absolute values of respective weights of one or more terms that each have a shared variable of the plurality of variables;
• compute an inverse temperature upper bound for the combinatorial optimization problem, wherein computing the inverse temperature upper bound includes estimating a minimum change in the energy function between successive timesteps of the plurality of timesteps at least in part by estimating, over the plurality of variables of the energy function, a minimum of:
• a difference between corresponding highest and second-highest absolute values of respective weights of a plurality of terms that each have a shared variable of the plurality of variables;
• or
• a one-variable minimum change in the energy function when a value of a variable of the plurality of variables is changed while respective values of each other variable of the plurality of variables are held constant;
• compute the solution to the combinatorial optimization problem at least in part by executing a Markov chain Monte Carlo (MCMC) algorithm over the plurality of timesteps, wherein:
• an inverse temperature of the MCMC algorithm is set to the inverse temperature lower bound during an initial timestep of the plurality of timesteps;
• and
• the inverse temperature of the MCMC algorithm is set to the inverse temperature upper bound during a final timestep of the plurality of timesteps;
• and
• output the solution.