Explanation of Adding a Variable When Converting QUBO to Ising#

Not all special-purpose quantum computers (SPQC) are designed to solve Ising problems that include linear terms. In order to solve a general Ising problem, we introduce an auxiliary spin variable sas_a and restate the problem as:

min⁡sa,s1,s2,...sN−∑i=1Nhisisa−∑i≠jJijsisj,\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 SPQC that does not support bias terms. The Ising problem has two degenerate solutions: [{si^}i=1N,s^a=1][\{\hat{s_{i}}\}_{i=1}^N, \hat{s}_{a} = 1] and [{−si^}i=1N,s^a=−1][\{-\hat{s_{i}}\}_{i=1}^N, \hat{s}_{a} = -1]. Where {si^}i=1N\{\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(s^)=min⁡s∈{−1,1}N−hTs−sTJs,J(\mathbf{\hat{s}}) = \min_{\mathbf{s}\in \{-1,1\}^N} -\mathbf{h}^T\mathbf{s} - \mathbf{s}^T\mathbf{J}\mathbf{s},

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

Ja(sˉ,s^a)=min⁡s∈{−1,1}N, sa∈{−1,1}−(hTs)sa−sTJs,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 (sˉ,s^a)(\mathbf{\bar{s}},\hat{s}_a) represents the optimal solution to the auxiliary Ising problem. Both sˉ\mathbf{\bar{s}} and s^\mathbf{\hat{s}} are N×1N\times1 spin vectors. If sa^=1\hat{s_{a}} = 1, then Ja(sˉ,1)J_a(\mathbf{\bar{s}},1) = J(s^)J(\mathbf{\hat{s}}). Below we prove that when sa^=−1\hat{s_{a}} = -1, Ja(sˉ,−1)J_a(\mathbf{\bar{s}},-1) = J(s^)J(\mathbf{\hat{s}}). Suppose the opposite is true:

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

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

Therefore, Ja(sˉ,s^a)=J(s^)J_a(\mathbf{\bar{s}},\hat{s}_a) = J(\mathbf{\hat{s}}). Note that the auxiliary Ising problem has two degenerate solutions (sˉ,1)(\mathbf{\bar{s}},1) and (−sˉ,−1)(-\mathbf{\bar{s}},-1), where sˉ\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 s^=sˉ⋅s^a\mathbf{\hat{s}} = \mathbf{\bar{s}} \cdot \hat{s}_a.