Explanation of Adding a Variable When Converting QUBO to Ising#

Not all Coherent Ising Machines (CIM) are designed to solve Ising problems that include linear terms. In order to solve a general Ising problem, we introduce an auxiliary spin variable s_a and restate the problem as:

\min_{s_a,s_1,s_2,...s_N} -\sum_{i=1}^N h_{i}s_{i}s_a - \sum_{i \neq j}J_{ij}s_{i}s_{j},

This restatement eliminates the linear terms, making it suitable for CIM that does not support bias terms. The Ising problem has two degenerate solutions: [\{\hat{s_{i}}\}_{i=1}^N, \hat{s}_{a} = 1] and [\{-\hat{s_{i}}\}_{i=1}^N, \hat{s}_{a} = -1]. Where \{\hat{s_{i}}\}_{i=1}^N represents the solution to the original Ising problem. Therefore, we can obtain the solution to the original problem from the solution to the auxiliary Ising problem.

Proof

The Ising problem we want to solve is:

J(\mathbf{\hat{s}}) = \min_{\mathbf{s}\in \{-1,1\}^N} -\mathbf{h}^T\mathbf{s} - \mathbf{s}^T\mathbf{J}\mathbf{s},

where \mathbf{\hat{s}} is the optimal solution. The auxiliary Ising problem is defined as:

J_a(\mathbf{\bar{s}},\hat{s}_a) = \min_{\mathbf{s}\in \{-1,1\}^N\text{,~}s_a\in\{-1,1\}} -(\mathbf{h}^T\mathbf{s})s_a - \mathbf{s}^T\mathbf{J}\mathbf{s},

where (\mathbf{\bar{s}},\hat{s}_a) represents the optimal solution to the auxiliary Ising problem. Both \mathbf{\bar{s}} and \mathbf{\hat{s}} are N\times1 spin vectors. If \hat{s_{a}} = 1, then J_a(\mathbf{\bar{s}},1) = J(\mathbf{\hat{s}}). Below we prove that when \hat{s_{a}} = -1, J_a(\mathbf{\bar{s}},-1) = J(\mathbf{\hat{s}}). Suppose the opposite is true:

  1. If J_a(\mathbf{\bar{s}},-1) < J(\mathbf{\hat{s}}), then J(-\mathbf{\bar{s}}) < J(\mathbf{\hat{s}}), which contradicts the optimality of \mathbf{\hat{s}}.

  2. If J_a(\mathbf{\bar{s}},-1) > J(\mathbf{\hat{s}})，then J_a(\mathbf{\bar{s}},-1) > J_a(\mathbf{\hat{s}},-1)，which also contradicts the optimality of (\mathbf{\bar{s}},-1).

Therefore, J_a(\mathbf{\bar{s}},\hat{s}_a) = J(\mathbf{\hat{s}}). Note that the auxiliary Ising problem has two degenerate solutions (\mathbf{\bar{s}},1) and (-\mathbf{\bar{s}},-1), where \mathbf{\bar{s}} is also the optimal solution to the original Ising problem. Thus, we can obtain the solution to the original problem from the solution to the auxiliary problem by \mathbf{\hat{s}} = \mathbf{\bar{s}} \cdot \hat{s}_a.