Solving Algorithms¶

Fixstars Amplify Annealing Engine (Amplify AE) utilizes an optimization algorithm based on simulated annealing. This page provides an overview of the Amplify AE algorithm and details internal processing steps.

GPU Annealing¶

Simulated annealing aims to minimize an objective function to solve optimization problems. It begins by generating an initial solution for the variable set, which is then iteratively improved. At each step, a temperature parameter governs the transition to a new state. Higher temperatures increase the probability of transitioning to states further from the current solution (those with a higher objective function value), while lower temperatures favor transitions to states closer to the current solution (those with a lower objective function value). Initially, with higher temperatures, the algorithm explores a wider range of possibilities, allowing for significant changes. As the temperature decreases, the search narrows, focusing on finer improvements to the solution. By gradually reducing the temperature, the algorithm seeks to converge on an optimal solution.

This process can be formulated as follows. Let \(T\) denote the current temperature, \(S\) the current state, \(S'\) a new state, and \(\varDelta f = f\left(S'\right) - f\left(S\right)\) the difference in the objective function \(f\). The transition probability \(P_{S \rightarrow S'}\) is expressed as (in the case of the Metropolis algorithm):

\[ P_{S \rightarrow S'} = \min \left( 1, \exp \left( -\varDelta f / T \right) \right) \]

A new state \(S'\) is generated, and the above equation is evaluated to probabilistically determine whether a state transition occurs. If the transition is accepted, the current state is updated to \(S'\). By repeating updates while decreasing the temperature \(T\) from high to low, improvement of the solution is expected.

Because this process is performed sequentially, simulated annealing is generally difficult to parallelize. While several parallelization approaches have been proposed, Amplify AE employs a unique parallelization algorithm [1] specifically designed to leverage the computational power of GPUs, enabling it to execute the entire search process efficiently and at high speed. Specifically, it utilizes GPU parallel computing to generate candidate next states and evaluate the objective function, enabling efficient exploration with multiple candidate transitions.

Note

Due to the use of pseudo-random numbers for probabilistic state transitions, different solutions may be obtained across multiple runs, even with the same input. Parallel computation on GPUs does not allow control over the order of calculations, meaning that even with a fixed pseudo-random number seed, consistent results cannot be guaranteed. Therefore, setting a seed value is not currently supported in Amplify AE.

On the other hand, in simulated annealing, scheduling the temperature changes is crucial. This temperature scheduling refers to determining the initial and final temperatures, as well as how the temperature decreases from the initial to the final value. Tuning the temperature schedule is essential for achieving high-precision solutions. To address this issue, Amplify AE features automatic temperature scheduling adjustment, allowing users to obtain optimal solutions without needing to configure temperature-related parameters. Conventional temperature schedules end the search after a specified number of steps. Amplify AE, in contrast, automatically determines the minimum unit of the search process based on the input problem and solving status. This is repeated continuously until the search continues until the specified solving time (time_limit_ms request parameter) elapses. Consequently, longer execution times increase the likelihood of obtaining higher-precision solutions.

Objective Function Optimization¶

Following the algorithm described above, a new state \(S'\) and the corresponding objective function value \(f\left(S'\right)\) are calculated for an input objective function as follows. First, we explain the optimization of the objective function in the absence of constraints.

Since Amplify AE accepts polynomials of binary variables as input, a new state \(S'\) is generated by flipping the value of a variable \(q\) using the operation \(q \leftarrow 1 - q\) (changing \(0\) to \(1\) or \(1\) to \(0\)). The resulting difference in the objective function, \(\varDelta f\), is expressed as:

\[ \varDelta f_{\rm{obj}}^q = f\left(S'\,|\,q \leftarrow 1 - q \right) - f\left(S \,|\,q\right) \]

From this value, the state transition probability \(P_{S \rightarrow S'}\) is calculated, and a uniform random number is generated to determine whether the state transition is accepted. If the transition is accepted, the current state \(S\) is updated to the new state \(S'\).

Constraint Optimization¶

When handling constraints in an annealing process, it is necessary to minimize the objective function for solutions that satisfy the given constraints. To obtain solutions that satisfy these constraints, one approach is to allow only state transitions that adhere to them. However, verifying whether candidate state transitions satisfy the constraints requires evaluating all constraints, which increases computational cost. Furthermore, restricting transitions to only those that satisfy the constraints can narrow the search space and may prevent reaching the optimal solution.

Therefore, Amplify AE addresses this by introducing penalty functions corresponding to the constraints, treating them as additional terms to the objective function. Essentially, the penalty function is \(0\) for solutions that satisfy the constraints and takes a positive value for those that do not. Minimizing the objective function while simultaneously driving the penalty function to \(0\) results in a solution that satisfies the constraints.

This approach is widely used when handling constraints in QUBO solvers such as quantum annealing and Ising machine hardware. During the search, deliberately allowing constraint-violating state transitions can broaden the search space.

Given a constraint \(c\) with penalty \(g_c\), similar to the objective function, the difference in the penalty function \(\varDelta g_c\) when flipping the variable \(q\) is defined as:

\[ \varDelta g_c^{q} = g_c\left(S'\,|\,q \leftarrow 1 - q \right) - g_c\left(S \,|\,q\right) \]

Furthermore, the difference in the objective function \(\varDelta f\) is reinterpreted as:

\[ \varDelta f = \varDelta f_{\rm{obj}}^q + w \sum_c \varDelta g_c^{q} \]

The state transition probability \(P_{S \rightarrow S'}\) is calculated from this \(\varDelta f\) to update the state.

Here, \(w \left(> 0 \right)\) represents the weight of the penalty function. It is important to note that the penalty function must be tuned appropriately to satisfy the constraints in the final state. If the weight of the constraints is too small relative to the change in the objective function, solutions that do not satisfy the constraints are more likely to be selected. Conversely, if the weight is too large, minimizing the objective function may become difficult. Achieving this balance is crucial for obtaining high-accuracy solutions. Amplify AE features an automatic penalty function weight adjustment, allowing users to achieve appropriate solutions without setting these parameters.

Amplify AE evaluates penalty functions in two ways, depending on user input:

(i) Default Mode

When the user provides constraint expressions, Amplify AE calculates the penalty function at runtime as an expression that monotonically increases with the constraint violation amount. In this case, Amplify AE generates the penalty function \(g_c\) as a function of the violation amount \(d\) that satisfies the following properties:

\[\begin{split} \begin{align*} g_c\left(d \right) & = \begin{cases} 0 & (d = 0; c \text{ is satisfied}) \\ \text{positive value} & (d > 0; c \text{ is not satisfied}) \end{cases} \\ g_c \left(d_1 \right) & = g_c \left(d_2 \right) \quad \text{for} \quad d_1 = d_2 \\ g_c \left(d_1 \right) & < g_c \left(d_2 \right) \quad \text{for} \quad d_1 < d_2 \end{align*} \end{split}\]

The penalty function is automatically generated based on the constraints entered by the user during the Amplify AE’s solving process. If the user wishes to specify the penalty function directly, use the PUBO mode.

(ii) PUBO Mode

When the user provides penalty functions instead of constraint conditions, the penalty value is evaluated using the specified penalty function. This operation mode is called PUBO mode. The penalty function must satisfy the following requirement:

\[ g_c\left(d \right) \ge 0 \]

In PUBO mode, the user directly specifies the penalty function \(g_c\) and its weight \(w_c\). Using these, the difference in state transitions is calculated as follows:

\[ \varDelta f = \varDelta f_{\rm{obj}}^q + w \sum_c w_c \varDelta g_c^{q} \]

The weight \(w\) applied to the entire penalty function is automatically adjusted by Amplify AE, as described previously. In PUBO mode only, control over this feature can be requested using the penalty_weight_calibration field in the request data. If this is disabled (false), \(w\) is fixed at 1.

On the other hand, \(w_c\) can be specified individually for each penalty function by the user, representing the relative weighting. The default value is \(w_c = 1\). In cases where a solution satisfying the constraints cannot be obtained, adjusting this value by the user can improve the solution accuracy.

Typically, when the violation amount \(d\) is 0, the value of the penalty function is also 0, indicating that the constraint is satisfied. As an option, a threshold \(d_{\text{th}}\) can be set to consider the violation amount below which the constraint is satisfied, even if the value of the penalty function value is not 0. This value needs to be set, for example, when setting the penalty for constraint conditions using penalty relaxation. Amplify AE uses this value to determine whether the obtained solution satisfies the constraints. When formulating using the Amplify SDK, \(d_{\text{th}}\) is automatically set to an appropriate value according to the properties of the penalty function.