Nonstoquastic catalyst for bifurcation-based quantum annealing of ferromagnetic $p$-spin model

Quantum annealing (QA) is a quantum metaheuristic for solving combinatorial optimization problems [1, 2, 3, 4, 5, 6, 7], and is related to adiabatic quantum computation [8, 9]. The target of QA is the ground state of the classical Ising model to which a combinatorial optimization problem is mapped [10]. Standard QA is formulated as a spin-1/2 Ising model with a time-dependent transverse field. The protocol of QA starts with the spins initialized to the superposition of the two orthogonal states $\ket{\pm 1}$ by the transverse field. By adiabatically decreasing the amplitude of transverse field, we can obtain the desired ground state corresponding to the optimal solution.

The performance of QA can be evaluated with a minimum energy gap between an instantaneous ground state and the first excited state. This can be understood with the quantum adiabatic theorem, which indicates that the annealing time necessary to obtain the desired ground state is inversely proportional to the square of the minimum energy gap [11, 12, 13]. It is empirically known that the minimum energy gap closes exponentially with increasing system size when a quantum system encounters a first-order phase transition during annealing. This is a serious problem for QA because the annealing time increases exponentially as the system size increases. The ferromagnetic $p$-spin model is a well-known example in which the first-order phase transition appears during QA [14]. In contrast, when the phase transition is second order, the minimum energy gap decreases polynomially as the system size increases. Then, in this case, we can find the ground state in polynomial time.

It is worth mentioning that standard QA is implemented with a stoquastic Hamiltonian, in which all nondiagonal elements of the matrix representation are real and nonpositive [15]. Since a system under a stoquastic Hamiltonian can be emulated classically without the sign problem, the standard QA is considered to have comparable performance to a classical algorithm. Therefore, whether a nonstoquastic catalyst, which is an additional Hamiltonian violating the stoquastic condition, can improve the performance of QA has been investigated. The mean-field analysis for QA with the $p$-spin model showed that a certain type of nonstoquastic catalyst is effective in changing the first-order phase transition to the second-order one [16, 17, 18, 19]. This is an interesting case in which a nonstoquastic catalyst leads to an exponential acceleration of QA. The numerical calculation [20] showed that QA under a nonstoquastic Hamiltonian has an advantage over standard QA. On the other hand, Ref. [21] showed that the energy gap in a Hamiltonian with a nonstoquastic catalyst is generally smaller than a stoquasticized Hamiltonian obtained by de-signing the nonstoquastic catalyst.

Recently, bifurcation-based QA (BQA) using Kerr-nonlinear parametric oscillators (KPOs) was studied [22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]. A KPO can generate a cat state (superposition of two coherent states) from a vacuum state by an adiabatic process. The idea of BQA originates from this cat-state generation process, which is referred to as the quantum bifurcation mechanism. While the Hamiltonian of BQA using the KPOs is described with bosonic operators, a spin formulation of BQA, which is described by the spin-1 operators, was also proposed in [34]. This spin formulation is designed to resemble the bifurcation mechanism of the KPO. In this formulation, each spin state is initially prepared in $\ket{0}$ and eventually becomes either $\ket{+1}$ or $\ket{-1}$. According to the effective spin model of the KPO studied in Ref. [35], BQA described with spin-1 operators can be regarded as the approximation model of BQA using KPO. Also, by adopting a spin-locking technique [36, 37], we can implement not only the conventional QA [38, 39] but also BQA described with the spin-1 operators with nitrogen-vacancy (NV) centers in diamonds [40]. The NV center in a diamond is a promising device for realizing quantum information processing because it has a long coherence time, such as a few milliseconds, even at room temperature [41, 42]. Therefore, the study of BQA will lead to the development of a novel experimental platform for QA. In addition, some studies suggest that BQA may have an advantage over conventional QA with the transverse field [28, 34]. However, the Hamiltonian of the spin formulation of BQA proposed in Ref. [34] is stoquastic. The natural question of whether a nonstoquastic catalyst will benefit BQA arises.

In this paper, we study the effect of a nonstoquastic catalyst in BQA described by the spin-1 operators. Here, we consider the $p$-spin model and propose a nonstoquastic catalyst to change the order of the phase transition. In order to analyze the phase transitions in stoquastic and nonstoquastic cases, we calculate the energy potential with the semiclassical approximation as in various QA studies [43, 44, 45, 46, 47, 48]. A previous study [48] showed that, for standard QA of the $p$-spin model with the nonstoquastic catalyst, the semiclassical analysis significantly predicts the location and order of the phase transitions, and agrees with the full quantum statistical-mechanical calculations [16]. Thus, the semiclassical analysis will also be practical for the current problem. We show that the proposed nonstoquastic catalyst is effective for changing the first-order phase transition, which appears in the stoquastic case, to the second-order one. To support the argument of the semiclassical analysis, we study the exact ground state and the minimum energy gap in a finite-size system by diagonalizing the Hamiltonian. We confirm that the instantaneous ground state obtained in the semiclassical analysis approximates the exact instantaneous ground state well. We also show that, as the system size increases, the minimum energy gap decreases exponentially in the stoquastic case and decreases polynomially in the nonstoquastic case.

This paper is organized as follows. In Sec. II, we introduce the spin formulation of BQA. In Sec. III, we formulate the Hamiltonian of the $p$-spin model and propose a nonstoquastic catalyst for BQA. In Sec. IV, we calculate the semiclassical potential and the order parameters to investigate the order of the phase transitions. In Sec. V, we discuss the effect of the proposed nonstoquastic catalyst in a finite-size system. We summarize this paper in Sec. VI. In Appendix A, we discuss an implementation of BQA with the NV centers in diamonds. We provide additional analyses and details of certain calculations in Appendixes B and C, respectively.

We recapitulate the spin formulation of BQA proposed in Ref. [34]. First, we define the $x$, $y$, and $z$ components of the spin-1 operators as

respectively. The eigenstates of $\hat{S}^{z}$ denote $\ket{0}$ and $\ket{\pm 1}$ as $\hat{S}^{z}\ket{m}=m\ket{m}$ for $m=0,\pm 1$. The Hamiltonian of BQA for an $N$-spin system is given by

where $s\in[0,1]$ is a dimensionless time parameter and $i$ indicates the index of a spin site. $A(s)$ is a positive function that takes a finite value at the middle of annealing, and $B(s)$ is a function increasing from a large negative value to a large positive value as time $s$ evolves. We assume that $A(s)$ and $B(s)$ are a Gaussian function and a linear function, respectively, as

The summation term in Eq. (2) is a driver Hamiltonian inducing the bifurcation mechanism. $\hat{H}_{p}$ represents a problem Hamiltonian that includes interactions between spins and local fields. BQA starts with the state $\otimes_{i}\ket{0}_{i}$, which is the ground state of the Hamiltonian (2) at $s=0$. By adiabatically evolving the system under the Hamiltonian (2) from $s=0$ to $s=1$, each spin state changes to $\ket{\pm 1}_{i}$, corresponding to the ground state of $\hat{H}_{p}$ that is our target.

To briefly review the bifurcation mechanism, we consider a single-spin system. The Hamiltonian is

We evaluate the instantaneous ground state numerically for the three $h$ cases. Figure 1(a) for $h=0$ shows that the final ground state is the superposition of $\ket{\pm 1}$. We can see the bifurcation mechanism around $s=0.5$, where the probability of the superposition state increases and the state $\ket{0}$ vanishes. This case corresponds to the cat-state generation of the KPO. When $h$ is positive (negative), the spin state becomes $\ket{+1}$ ($\ket{-1}$), as shown in Figs. 1(b) and 1(c).

Hereafter, we consider the ferromagnetic $p$-spin model in the spin formulation of BQA. The Hamiltonian is as follows:

For odd $p$, the ground state of the $p$-spin model is $\otimes_{i=1}^{N}\ket{+1}_{i}$, and for even $p$, the ground state is doubly degenerate, $\otimes_{i=1}^{N}\ket{+1}_{i}$ and $\otimes_{i=1}^{N}\ket{-1}_{i}$. Note that this $p$-spin model reduces to the Grover problem for the limit of $p\rightarrow\infty$.

This Hamiltonian (5) is stoquastic, and the first-order phase transition appears during the time evolution (we discuss this in the next section). We then propose the following interaction as a nonstoquastic catalyst:

The operator (7) switches the spin state between $\ket{+1}_{i}$ and $\ket{-1}_{i}$ in a way similar to the Pauli $X$ operator. The catalyst (6) is inspired by a nonstoquastic $XX$ interaction removing the first-order phase transition in standard QA of the $p$-spin model [16, 17, 18]. We consider the following Hamiltonian:

where $C$ is the amplitude of the proposed nonstoquastic catalyst. The Hamiltonian (III) becomes nonstoquastic for $C>0$, and setting $C<0$ corresponds to the de-signed stoquastization studied in Ref. [21]. We discuss a possible realization of this Hamiltonian by using NV centers in diamonds in Appendix A. It is worth mentioning that the typical energy scale of the interaction between the NV centers is tens of kilohertz when we realize our proposed method with the NV centers in diamonds, as we discuss in Appendix A. Therefore, throughout this paper, we assume that the energy is scaled by a unit of $10$ kHz.

To investigate the phase transitions in BQA under the Hamiltonian (III), we use the semiclassical spin coherent state for the spin-1 operators [49] defined as the product state

All spins are assumed to have the same angular variables $\theta$, $\phi$, $\alpha$, and $\beta$. The semiclassical potential per spin is derived from the expectation value of the Hamiltonian in the spin coherent state (IV) as

The $\theta$, $\phi$, $\alpha$, and $\beta$ to minimize the semiclassical potential are denoted as $\theta_{\min}$, $\phi_{\min}$, $\alpha_{\min}$, and $\beta_{\min}$, respectively. The ground state in the semiclassical approximation is given by $\ket{\psi_{\textrm{SC,GS}}}=\ket{\psi_{\textrm{SC}}(\theta_{\min},\phi_{\min},\alpha_{\min},\beta_{\min})}$. Thus, the order parameter at the semiclassical limit can be calculated as

Note that since the spin coherent state (IV) does not cover superposition of $\otimes_{i}\ket{+1}_{i}$ and $\otimes_{i}\ket{-1}_{i}$, the present analysis might be insignificant for even $p$ cases with the degenerate ground state. For convenience, we arbitrarily consider the case where the instantaneous ground state finally becomes $\otimes_{i}\ket{+1}_{i}$. Therefore, we restrict the domains of $\theta$ and $\phi$ to $0\leq\theta\leq\pi$ and $0\leq\phi\leq\pi/2$.

First, we consider the stoquastic case $C=0$, where $\alpha=\beta=0$ clearly gives the ground state. Figure 2 shows the numerical results for $\theta_{\min}$, $\phi_{\min}$, and the order parameter $m$ for $p=5$. Figure 2(a) shows $\theta_{\min}$ increases from zero with $\phi_{\min}=\pi/2$ in the first half. This means that the amplitude of $\ket{0}_{i}$ in the instantaneous ground state decreases, and those of $\ket{+1}_{i}$ and $\ket{-1}_{i}$ increase. After the discontinuous change in $\theta_{\min}$ and $\phi_{\min}$, we obtain $\theta_{\min}=\pi$ and $\phi_{\min}=0$, which gives $\ket{\psi_{\textrm{SC,GS}}}=\otimes_{i}\ket{+1}_{i}$. We can see in Fig. 2(b) that the order parameter $m$ changes discontinuously at $s\approx 0.550$, where the first-order phase transition appears.

The results for the nonstoquastic cases are plotted in Fig. 3. In Fig. 3(a) for $C=1.4$, $\phi_{\min}$ deviates from $\pi/2$ at $s\approx 0.520$. Correspondingly, the order parameter is continuously away from zero, which is a signature of a second-order transition. However, the first-order phase transition occurs at $s\approx 0.522$. By setting a significant amplitude, such as $C=5$, as shown in Fig. 3(b), the phase transition becomes completely second order, where the order parameter changes continuously from $0$ to $1$. Therefore, in order to resolve the first-order phase transition, the proposed nonstoquastic catalyst (6) is effective. Note that we obtain $\alpha_{\min}=\beta_{\min}=0$ in both Figs. 3(a) and 3(b). This is due to the absence of an imaginary component in the Hamiltonian (III). In Appendix B we give the situation where the driver Hamiltonian is rotated around the $z$ axis and the total Hamiltonian has an imaginary component.

Next, we discuss de-signed stoquastization [21] of the nonstoquastic Hamiltonian (III). In Fig. 4, we plot the order parameters for two negative-$C$ cases. The first-order phase transition appears when $C=-0.8$ [Fig. 4(a)], and the order parameter $m$ stays zero for $C=-0.9$ [Fig. 4(b)] during time evolution. Thus, negative $C$ is ineffective for the present problem.

We also plot the order parameter as a function of coefficients $A$ and $B$ in the driver Hamiltonian. The results are plotted in Fig. 5. In Fig. 5(a) for the stoquastic case, the system encounters the first-order phase transition by increasing $B$ regardless of the value of $A$. Next, we show the plots for $C>0$ in Figs. 5(b)-5(d). The orange dashed curves indicate the location where the second-order phase transition appears. These curves are calculated using the following conditions

In this calculation, we assume that the second-order phase transition occurs at the point where $\phi_{\min}$ continuously deviates from $\pi/2$ and the ground state has $\alpha_{\min}=\beta_{\min}=0$. Figure 5(b) shows the case of $C=1.4$. The first-order transition appears even if we take the path across the orange dashed curve. The blue curve in Fig. 5(b) is the same as the order parameter plotted in Fig. 3(a). In Fig. 5(c), we can find the path along which the order parameter continuously changes for $C=2$. However, the first-order phase transition remains for the path with a small $A$. Although $C$ is made larger, a large $A$ is necessary to avoid the first-order phase transition, as shown in Fig. 5(d).

Figure 6 shows the phase diagrams for $3\leq p\leq 8$ obtained from the order parameter, which is given by the semiclassical analysis. We use Eq. (3) for $A(s)$ and $B(s)$, and consider two $A_{0}$ cases. The colored curves indicating the first-order phase transition extend from points on the axis $C=0$. In Fig. 6(a), the curves for $p=3,4$, and $5$ are terminated at finite $C$. Therefore, we can find the paths to avoid the first-order phase transitions for $p=3,4$, and $5$ by tuning the amplitude $C$. However, as long as we use the value of $A_{0}=2$, the curves for the first-order phase transitions for $6\leq p\leq 8$ are unavoidable. On the other hand, Fig. 6(b) shows that, if we adopt $A_{0}=3$, we can circumvent those curves with relatively small $C$. However, Fig. 7 shows that we need to set larger $A_{0}$ again to avoid the first-order phase transition in the higher-$p$ cases. It is worth mentioning that for conventional QA with qubits it becomes more difficult to avoid the first-order phase transition as we increase the value of $p$ [16, 17], which is similar to our case. More specifically, we need a careful adjustment of the amplitude parameter to avoid a first-order phase transition when $p$ is high [16, 17].

Let us consider the effect of the proposed nonstoquastic catalyst in a finite-size system to discuss the validity of the semiclassical approximation. We can obtain the exact ground state $\ket{\psi_{\mathrm{GS}}}$ by diagonalizing the Hamiltonian (III). The details of the calculation are shown in Appendix C. We plot the order parameter for the system with $N=96$ spins, which is denoted as $m_{N=96}$, in Fig. 8. This result agrees with the semiclassical analysis shown in Figs. 2 and 3. Next, we calculate the fidelity between the semiclassical state $\ket{\psi_{\mathrm{SC,GS}}}$ and the exact ground state $\ket{\psi_{\mathrm{GS}}}$, namely, $|\bra{\psi_{\mathrm{SC,GS}}}\ket{\psi_{\mathrm{GS}}}|^{2}$. The fidelity for $p=5$ is shown in Fig. 9. We consider three values of $C$ and find the fidelity is almost $1$ except around the point of the phase transition in each case. A possible reason for the sudden decrease in fidelity is that the location in $s$ for the phase transitions to occur in the finite-size calculation is slightly different from that in the semiclassical analysis. These results suggest that the semiclassical state can reasonably approximate the exact ground state.

By calculating the eigenvalues of the Hamiltonian (III), we can evaluate the minimum energy gap between the instantaneous ground state and the first excited state during annealing. Figure 10 shows that the minimum energy gap exponentially (polynomially) decreases versus the system size $N$ in the stoquastic (nonstoquastic) case. For $N\geq 45$, the gap in the nonstoquastic case becomes larger than that in the stoquastic case. Figure 10 is clear evidence that the proposed catalyst can qualitatively accelerate the present annealing protocol.

We considered the $p$-spin model in BQA described by the spin-1 operators and proposed a nonstoquastic catalyst. We used the semiclassical analysis with the spin coherent state to investigate the phase transitions in stoquastic and nonstoquastic cases. We found that, for specific cases, the proposed nonstoquastic catalyst (6) is effective for reducing the first-order phase transition appearing in the stoquastic case to the second-order one. This means that the catalyst will lead to performance improvement. One needs a sufficient amplitude of the nonstoquastic catalyst and appropriate control of the driver Hamiltonian to remove the first-order phase transition. Nevertheless, if the amplitude $C$ is small and the system has a first-order phase transition, the performance of BQA will be improved. As we saw in Fig. 3(a), the jump in the order parameter at the first-order phase transition in the nonstoquastic case is less than the one in the stoquastic case. The jump width corresponds to the energy-barrier width, which affects the probability that the system will reach the desired ground state thorough the quantum tunneling effect. Thus, a nonstoquastic catalyst would increase the probability and help with the ground-state search even when the first-order phase transition occurs.

We also evaluated the scaling of the energy gap by diagonalizing the Hamiltonian (III), and the results agree with our claim. The fidelity shows that the semiclassical analysis is accurate enough to predict the exact ground state. Since the semiclassical analysis is based on the static approximation, we could not evaluate the actual time to satisfy the adiabatic condition. However, as shown in a previous paper [48], the semiclassical analysis provides a powerful tool to predict where the phase transition occurs, and we use it for the case of BQA.

We numerically calculated the endpoints of the curves for the first-order phase transitions in the phase diagram in Fig. 6. On the other hand, it was shown that for standard QA [50] the exact endpoints can be analytically derived for the mean-field model with the nonstoquastic catalyst. Therefore, for our problem, we also might be able to predict the endpoints more precisely, which is left for future study.

We note that the $p$-spin model with $p=4$ can be regarded as the mean-field approximation of the Lechner-Hauke-Zoller (LHZ) model with local four-body interactions [51, 52]. The LHZ model is considered practical architecture for BQA with KPOs to solve a fully connected problem Hamiltonian [28, 29, 32]. Thus, our results for the $p$-spin model will be helpful in designing real quantum devices. However, to implement BQA with a nonstoquastic catalyst by using KPOs, we need to develop a framework in the bosonic system similar to our proposal. We also leave this for future work.

For further understanding of a nonstoquastic catalyst in BQA, it is desirable to study other instances, such as the weak-strong cluster problem, which also has a first-order phase transition [19, 53]. Additionally, developing other avenues for improving BQA is interesting. Various approaches for improving standard QA have been studied, for example, inhomogeneous driving [52, 54, 55], reverse annealing [56, 57, 58], and counterdiabatic driving [59, 60, 61, 62, 63]. Whether these are also applicable to BQA is an interesting topic.