Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing

The annealing time evolution equation is usually expressed using the adimensional time $s=t/T$, where $t$ and $T$ denote time and total annealing time, respectively. A QA problem of an $n$ spin system can be expressed as the following equation [1]:

$\displaystyle H(s)=(1-s)H_{B}+sH_{P}.$

(1)

In QA, ${H_{B}}$ is a transverse magnetic field added by the Pauli $x$-matrix $\sigma_{i}^{x}$ as

$\displaystyle H_{B}=\sum_{i=0}^{n-1}\sigma_{i}^{x}\ .$

(2)

Equation (1) using Eq. (2) is called stoquastic quantum annealing. Here, the problem Hamiltonian is expressed by the Ising coefficients as

$\displaystyle H_{P}=\sum_{i<j}J_{ij}\sigma_{i}^{z}\sigma_{j}^{z}+\sum_{i}h_{i}\sigma_{i}^{z}.$

(3)

Equation (3) consists of the two-spin interaction coefficient ${J_{ij}}$ and the longitudinal magnetic field interaction coefficient ${h_{i}}$.

It is well known that Quadratic Unconstrained Binary Optimization (QUBO) problems are encoded by Ising Hamiltonians. The Ising energy can be written by QUBO variables $q_{i}\in\{0,1\}$ instead of Ising spin variables $\sigma_{i}^{z}\in\{-1,1\}$:

	$\displaystyle H_{P}$	$\displaystyle=$	$\displaystyle 4\sum_{i=0}^{n-1}\sum_{j=0,i<j}^{n-1}J_{ij}q_{i}q_{j}$		(4)
			$\displaystyle+2\sum_{i=0}^{n-1}\sum_{j=0,i<j}^{n-1}(-J_{ij}+h_{i})q_{i}+\sum_{i=0}^{n-1}\sum_{j=0,i<j}^{n-1}J_{ij}$
			$\displaystyle-\sum_{i=0}^{n-1}h_{i}.$

When we use QUBO coefficients $Q_{ij}$ and $b_{i}$ instead of Ising coefficients, $H_{P}$ is rewritten by:

$\displaystyle H_{P}=Q_{ij}q_{i}q_{j}+b_{i}q_{i}+\text{const.},$

(5)

where const. is

$\displaystyle\text{const.}=\sum_{i=0}^{n-1}\sum_{j=0,i<j}^{n-1}J_{ij}-\sum_{i=0}^{n-1}h_{i}.$

(6)

The quantum adiabatic theorem characterizes the sufficiently slow rate required for evolution to move from the initial ground state to the final ground state by giving a lower bound on the total time $T_{\text{anneal}}$ [2]:

$\displaystyle T_{\text{anneal}}\gg\dfrac{\epsilon}{\Delta_{\text{min}}^{2}},$

(7)

where $\epsilon=\text{max}_{s}|\braket{E_{1}(s)}{\frac{dH}{ds}}{E_{0}(s)}|$ and $\Delta_{\text{min}}=\text{min}_{s}\ (E_{1}(s)-E_{0}(s))$ called “min-gap”. $E_{0}(s)$ and $E_{1}(s)$ denote the eigenvalues of the ground state $\Ket{E_{0}(s)}$ and the first excited state $\Ket{E_{1}(s)}$, respectively. They can be directly calculated from $H_{P}$. On the other hand, $\Ket{\tilde{E}_{0}(T)}$ is defined as the final ground state obtained by Eq. (1), which depends on total annealing time $T$. When total annealing time $T$ in Eq. (1) is longer than $T_{\text{anneal}}$, $\epsilon$ can make $|\braket{E_{0}(1)}{\tilde{E}_{0}(1)}|$ arbitrarily close to 1 [2]. For all of the problems that we simulate in Sec. 4, $\epsilon$ is of order a typical eigenvalue of $H_{P}$ and is not too big, so the size of $T_{\text{anneal}}$ is governed by $\Delta_{\text{min}}^{-2}$. We use the approximated annealing time $T_{\text{approx}}=\Delta_{\text{min}}^{-2}$ for order-of-magnitude estimate.

Anti-crossings are useful for the analysis of physical phenomena happening during QA, and are the specific behavior of the two lowest eigenvalues when the min-gap occurs around the anti-crossing point $s^{*}$ [31]:

$\displaystyle E^{\pm}(s)=E(s^{*})+B(s-s^{*})\pm\dfrac{1}{2}[\Delta^{2}_{\text{min}}+A^{2}(s-s^{*})^{2}]^{1/2},$

(8)

where $A$ and $B$ are the difference and the mean of the slopes of the asymptotes of the hyperbola, respectively. An anti-crossing at a first-order phase transition during the evolution occurs in the presence of an exponentially small min-gap. Choi has suggested a new parametrization of the physical phenomenon to study the occurrence of anti-crossings during adiabatic quantum computation [24]. Recently, Choi has applied parametrization to non-stoquastic quantum annealing [27]. Braida and Martiel have suggested another expression of the min-gap that is more general [28]. In Sec. 4, the min-gaps before/after the ELTIP are discussed.

We express the square of coefficients of the instantaneous eigenstates $\Ket{E_{0}(s)}$ in terms of the eigenstates $\Ket{E_{k}(1)}$ of the final Hamiltonian [24]:

$\displaystyle a_{k,0}(s)$

$\displaystyle=$

$\displaystyle|\braket{E_{k}(1)}{E_{0}(s)}|^{2}.$

(9)

That is, the square of a coefficient of the instantaneous ground state $a_{0,0}(s)=|\braket{GS}{E_{0}(s)}|^{2}$ is the weight (or overlap) of the solution state with the instantaneous ground state at time $s$. Similarly, $a_{1,0}(s)=|\braket{FS}{E_{0}(s)}|^{2}$ is the weight (or overlap) of the first excited state (which possibly corresponds to the local minima of the problem) with the instantaneous ground state at time $s$. At $s=1$, we have $a_{0,0}(1)=1$ and $a_{1,0}(1)=0$. We use min-gaps to evaluate the effectiveness of the ELTIP. We also observe the time evolution of $a_{0,0}(s)$ and $a_{1,0}(s)$, which has the correlation to min-gaps.

We use the non-stoquastic Hamiltonian [16, 17, 18, 19] for comparison. The annealing Hamiltonian including the non-stoquastic Hamiltonian introduced by Seki and Nishimori [16] is expressed as

$\displaystyle H(s)=s\{\lambda H_{P}+(1-\lambda)H_{\text{AFF}}\}+(1-s)H_{B},$

(10)

where $H_{\text{AFF}}$ denotes the antiferromagnetic interaction which has a two-spin flip effect:

$\displaystyle H_{\text{AFF}}=+N\left(\dfrac{1}{N}\sum_{i=0}^{n-1}\sigma_{i}^{x}\right)^{2}.$

(11)

The initial Hamiltonian has $s=0$ and $\lambda$ is arbitrary, and the final one has $s=\lambda=1$.

The connection between local minima in the problem Hamiltonian designed by MIS and first order quantum phase transitions (QPT) during an adiabatic quantum computation was investigated by Amin and Choi [25, 26]. QPT can be easily generated by using the balance of the MIS to make the eigenvalues of the ground state and the first excited state closer together and to separate the eigenvalues of the other states [25, 26]. Therefore, we use the MIS to design problems that cause QPT and use it for anti-crossing mitigation effect evaluation.

We use the 5-spin MIS problems [24] to compare the effectiveness of the non-stoquastic Hamiltonian and the ELTIP because of the design simplicity and good visibility of numerical results. An MIS problem shown in Fig. 2(a) is used to demonstrate the effectiveness of the ELTIP.

As an MIS problem, only the weights $b_{i}$ are important, but the coupling constants $Q_{ij}$ of 6.08 in Fig. 2(a) are not important. In other words, the problem with the other coupling constants can be regarded as the same MIS. However, whole energy landscapes are changed by the coupling constants, which affects QA time evolution. Therefore, the coupling constants must be fixed for the evaluation of QA time evolution and conversion. Figure 2(a) is designed to generate the anti-crossing between the ground and the first states, referred to in Ref [24]. Note that Ref [24] describes the MIS problems by the QUBO form, therefore Fig. 2(a) is denoted by the QUBO form. The ELTIP of $H_{0}=U_{0}HU_{0}^{\dagger}$ in Eq. (17) is applied to the problem shown in Fig. 2(a), and a transformed problem is shown in Fig. 2(b). Compared with the original problem in Fig. 2(a), the transformed problem in Fig. 2(b) has additional edges. From the viewpoint of obtaining the lowest eigenvalue and state, the problem transformed by the ELTIP is equivalent to the problem before transformation. Note that the ELTIP changes the physical picture. Therefore, the ELTIP can reduce the difficulty of solving the Ising problems with QA, while it cannot be used to analyze the physical phenomena in the original problems.

The QUBO and corresponding Ising coefficients with the ELTIP process are summarized in Table. 1. The ELTIP can be used for Ising problems. Therefore, once the original QUBO problem is written in the Ising problem (the first line to the second line in Table. 1), then the ELTIP is applied to the Ising problem (the second line to the third line in Table. 1). Finally, the Ising coefficient with the ELTIP is converted to the QUBO form (the third line to the fourth line in Table. 1).

Figure 2(a) and the first line in Table. 1, are an example in the case of $\Delta b_{1,3}=b_{1}-b_{3}=-5.96-(-6)=0.04$. It is well known that the energy landscape affects the convergence of annealing. By changing $\Delta b_{1,3}$, the energy landscape almost remains, but the energy gap between the final ground state and the final first excited state is tunable. Problems of $\Delta b_{1,3}=0.01,0.02,0.04,0.06,0.08$ will be simulated in the next subsection.

The energy gaps of the problems are shown in Fig. 3, where the energy gaps are $E_{1}(s)-E_{0}(s)$. We compare time evolution of the stoquastic quantum annealing, the non-stoquastic quantum annealing, and the stoquastic quantum annealing with the ELTIP transformation. $s^{*}$ is defined as $s$ when the min-gap occurs. $E_{1}(1)-E_{0}(1)$ is called the final gap, which equals to $\Delta b_{1,3}$. In the case of the stoquastic quantum annealing, the reduction of min-gap is much larger than that of the final gap. As the final gap decreases, $s^{*}$ approaches the final state. In the case of the non-stoquastic quantum annealing, the reduction of min-gap is not proportional to that of final gap. The non-stoquastic quantum annealing effectively mitigates the anti-crossing for the smallest final gap. However, as the final gap increases, the mitigation of the anti-crossing is reduced. For the largest final gap in our case, the anti-crossing is enhanced, although $s^{*}$ is not so changed. As shown in Fig. 3(c), the ELTIP eliminates the anti-crossing for all the final gaps. The min-gap is achieved near the end of the annealing, in all the final gaps.

According to Eq. (7), the approximated annealing time $T_{\text{approx}}=\Delta_{\text{min}}^{-2}$ determines the lower limit of the annealing time. We compared the time evolution of $a_{k,0}(s)\ (k=0,1,...,5)$ in the original and the transformed problems as shown in Fig. 4. Left and right plots are the instantaneous ground state represented by the final eigenstates with the final gap of 0.01 and 0.08, respectively. Figures 4(a) and 4(b) are the stoquastic annealing time evolution. For both energy gaps, near $s^{*}$ where anti-crossing occurs, the population ratios of the ground state and the first excited state are rapidly switched. The switching speed, namely spin-polarity flipping speed of the final gap 0.01 is much faster than that of 0.08. A wider gap weakens the flipping speed which is one of the characteristics of QPT. In the case of the non-stoquastic Hamiltonian in Fig. 4(c), the rapid transition from the first excited state to the ground state in Fig. 4(a) is obviously mitigated. On the other hand, in Fig. 4(d), the slope around $s^{*}$ becomes steeper than that of Fig. 4(b) of the stoquastic annealing. $T_{\text{approx}}$ defined in Sec. 2.1 in the case of the non-stoquastic Hamiltonian with $\Delta b_{1,3}=0.08$ is 10 times longer than the stoquastic Hamiltonian, and is almost comparable to the case when $\Delta b_{1,3}=0.01$ of the non-stoquastic Hamiltonian. The ELTIP shortens $T_{\text{approx}}$ of all the problems where the anti-crossing occurs. As a result, the ELTIP eliminates the rapid population inversion between the ground state and the first excited state which is observed in QPT. The ELTIP reduced the approximated annealing time $T_{\text{approx}}$ by a factor of $10^{4}$ with $\Delta b_{1,3}=0.01$ and $10^{2}$ with $\Delta b_{1,3}=0.08$. The rest of four ELTIPs $H_{1}$ to $H_{4}$ shows similar results.