Enhancing quantum annealing performance by a degenerate two-level system
Shohei Watabe Yuya Seki Shiro Kawabata




  
^1 Department of Physics, Faculty of Science Division I, Tokyo University of Science, Shinjuku, Tokyo 162-8601, Japan.
^2 Nanoelectronics Research Institute, National Institute of Advanced Industrial Science and Technology (AIST),
1-1-1 Umezono, Tsukuba, Ibaraki 305-8568, Japan.










 
Quantum annealing is an innovative idea and method for avoiding the increase of the calculation cost of the combinatorial optimization problem. Since the combinatorial optimization problems are ubiquitous, quantum annealing machine with high efficiency and scalability will give an immeasurable impact on many fields. However, the conventional quantum annealing machine may not have a high success probability for finding the solution because the energy gap closes exponentially as a function of the system size. To propose an idea for finding high success probability is one of the most important issues. 
Here we show that a degenerate two-level system provides the higher success probability than the conventional spin-1/2 model in a weak longitudinal magnetic field region. 
The physics behind this is that the quantum annealing in this model can be reduced into that in the spin-1/2 model, 
where the effective longitudinal magnetic field may open the energy gap, which suppresses the Landau–Zener tunneling providing leakage of the ground state. 
We also present the success probability of the Λ-type system, which may show the higher success probability than the conventional spin-1/2 model. 




Enhancing quantum annealing performance by a degenerate two-level system
    Shohei Watabe^1,2, Yuya Seki^2, and Shiro Kawabata^2
    December 30, 2023
========================================================================







§ INTRODUCTION



Quantum annealing is an interesting approach for finding the optimal solution of combinatorial optimization problems by using the quantum effect <cit.>.
The combinatorial optimization problems are ubiquitous in the real social world, therefore the spread of quantum annealing machine with high efficiency and high scalability will give impacts and benefits on many fields, such as an industry including drug design <cit.>, financial portfolio problem <cit.>, and traffic flow optimization <cit.>. 
After the commercialization of superconducting quantum annealing machine by D-Wave Systems inc. <cit.>, hardware has been investigated and developed <cit.>. 
    
However, there are bottlenecks for implementing scalable quantum annealing machine; for the conventional and scalable quantum annealing machine may not have a high success probability for finding the solution of a combinatorial optimization problem because of the emergence of the first order phase transition, where the energy gap between ground state and the first exited state closes exponentially as a function of the system size <cit.>. 
In this case, it necessitates an exponentially long annealing time for finding the solution of the problem <cit.>. 
In the case of the second oder phase transition, on the other hand, an annealing time for finding the solution may scales polynomially as a function of the system size <cit.>. 


To propose an idea for finding high success probability is one of the most important and challenging issue in the field of quantum annealing. 
One of the approaches for obtaining the high success probability is to engineer the scheduling function for the driving Hamiltonian and the problem Hamiltonian, such as a monotonically increasing scheduling function satisfying the local adiabatic condition <cit.>, the reverse quantum annealing <cit.> implemented in D-wave 2000Q <cit.>, inhomogeneous sweeping out of local transverse magnetic fields <cit.>, and a diabatic pulse application <cit.>. 
Another is to add an artificial additional Hamiltonian for suppressing the emergence of the excitations with avoiding the slowing down of annealing time, 
which is called shortcuts to adiabaticity by the counterdiabatic driving <cit.>, and to add an additional Hamiltonian for avoiding the first order phase transition <cit.>.  
In this paper, we study the possibility of other approach: to employ a variant spin, such as a qudit, in the quantum annealing architecture. 


Recently, two of the authors have studied the quantum phase transition in a degenerate two-level spin system, called the quantum Wajnflasz–Pick model, where an internal spin state is coupled to all the same energy internal states with a single coupling strength, and to all the different energy internal states with the other single coupling strength <cit.>. 
In the earlier study, this model is found to show a several kinds of phase transition while annealing; single or double first-order phase transitions as well as a single second-order phase transition, depending on an internal state coupling parameter <cit.>, which suggests that the quantum annealing of this model may be controlled by an internal state tuning parameter. 
However, the study is based on the static statistical approach using the mean-field theory, because only the order of the phase transition has been interested in. 
Therefore, the enhancement of the success probability for quantum annealing based on degenerate two-level systems is not clear yet. 
Furthermore, they employed a fully-connected uniform interacting system, and it is unclear whether their idea works that a double (or even-number of) first-order phase transition while annealing would bring the system back into the ground state at the end of the annealing, where the even number of the Landau–Zener tunneling may happen with respect to the ground state. 

In the present paper, we clarify the success probability of the quantum annealing in the quantum Wajnflasz–Pick model, focusing on (i) the Schrödinger dynamics, (ii) eigenenergies, and (iii) non-uniform effects of the spin-interaction as well as the longitudinal magnetic field. 
We find that the quantum Wajnflasz–Pick model is more efficient than the conventional spin-1/2 model in the weak longitudinal magnetic field region as well as in the strong coupling region between degenerate states. 
We also find that the quantum Wajnflasz–Pick model is reducible into a spin-1/2 model, where effect of the transverse magnetic field in the original Hamiltonian emerges in the reduced Hamiltonian not only as the effective transverse magnetic field but also as the effective longitudinal magnetic field. 
As a result, this model may provide the higher success probability in the case where the effective longitudinal magnetic field opens the energy gap between the ground state and the first excited state. 
We also evaluate the success probability in another variant spin, a Λ-type system <cit.>, which has three internal levels. 
This model also shows the higher success probability than the conventional spin-1/2 model in the weak magnetic field region. 

A multilevel system is ubiquitous, which can be seen, for example, in degenerate two-level systems in atoms <cit.>, 
Λ-type atoms <cit.>, 
Λ-, V-, Θ- and Δ-type systems in the superconducting circuits <cit.> as well as Λ-type systems in the nitrogen-vacancy centre in diamond <cit.>. 
We hope that insights of our results in the degenerate two-level system and knowledge of their reduced Hamiltonian inspire and promote further study as well as future engineering of quantum annealing. 




§ QUANTUM WAJNFLASZ–PICK MODEL



A conventional quantum annealing consists of the spin-1/2 model, where the time dependent Hamiltonian is given by <cit.> 

    Ĥ (s) = s Ĥ_z +  ( 1 - s  ) Ĥ_x,

where Ĥ_z,x are a problem and driver Hamiltonian, respectively, and s ≡ t/T is the time t ∈ [0,T] scaled by the annealing time T. 
The problem Hamiltonian  Ĥ_z with the number of spins N, which encodes the desired optimal solution, has a non-trivial ground state. 
In contrast, the driver Hamiltonian Ĥ_x has a trivial ground state, where the driver Hamiltonian Ĥ_x must not be commutable with the problem Hamiltonian Ĥ_z. 
A problem Hamiltonian and driver Hamiltonian are typically given by 

    Ĥ_z ≡    - ∑_i ≠ j ^N J_ijσ̂_i^z σ̂_j^z  - ∑_i^N h_i^z  σ̂_i^z, 
    	
    Ĥ_x ≡    - ∑_i^N h_i^x σ̂_i^x ,

where σ̂^x,z are the Pauli matrices, J_ij is the coupling strength between spins, h_i^z is the local longitudinal magnetic field, and h_i^x is the local transverse magnetic field. 
The time-dependent total Hamiltonian Ĥ(s) gradually changes from the driver Hamiltonian Ĥ_x to the problem Hamiltonian Ĥ_z. 
If the Hamiltonian changes sufficiently slowly, the quantum adiabatic theorem guarantees that the initial quantum ground state follows the instantaneous ground state of the total Hamiltonian <cit.>. 
We can thus finally obtain a non-trivial ground state of the problem Hamiltonian starting from the trivial ground state of the deriver Hamiltonian making use of the Schrödinger dynamics. 






The quantum Wajnflasz–Pick model is a quantum version of the Wajnflasz–Pick model <cit.>, which can describe one of the interacting degenerate two-level systems. In the language of the quantum annealing, 
the problem Hamiltonian and the driver Hamiltonian are respectively given by <cit.> 

    Ĥ_z ≡    - ∑_i ≠ j ^N J_ijτ̂_i^z τ̂_j^z  - ∑_i^N h_i^z  τ̂_i^z, 
    	
    Ĥ_x ≡    - ∑_i^N h_i^x τ̂_i^x.
 
(Schematic picture of this model is shown in Fig. <ref>.)
The Hamiltonian of this model can be simply obtained by replacing the Pauli matrices σ̂^x,z in Eqs. (<ref>) and (<ref>) with the spin matrices of the quantum Wajnflasz-Pick model τ̂^x,z. 
The spin operator τ̂^z is given by <cit.> 

    τ̂^z ≡ diag  ( +1, ⋯, +1_g_ u, -1, ⋯, -1_g_ l),

where g_ u(l) is the number of the degeneracy of the upper (lower) states.  
The spin-operator τ̂^x in the driver Hamiltonian is given by 

    τ̂^x ≡1/c[       A (g_ u) 1 (g_ u, g_ l); 1 (g_ l, g_ u)       A (g_ l) ],

where A (l) is a (l× l) matrix with the off-diagonal term ω, given by 

    A (l) ≡[   0   ω   ⋯   ω; ω^*   0   ⋱   ⋮;   ⋮   ⋱   ⋱   ω; ω^*   ⋯ ω^*   0 ].

Here, ω is a parameter of the internal transition between the degenerated upper/lower states. 
The matrix 1 (m,n) is the (m × n) matrix, where all the elements is unity, which gives the transition between the upper and lower states.  
The constant c is the normalization factor, where the maximum eigenvalue is normalized to be +1, so as to be equal to the maximum eigenvalue of τ̂^z. 

 

In the following, for the consistency to the earlier work <cit.>, we consider a uniform transverse field h_i^x ≡ 1, and also take the parameter of the internal transition to be real ω = ω^* with ω > -1. 
In the case where (g_ u, g_ l) = (2,1), we have 

    τ̂^z ≡[   1   0   0;   0   1   0;   0   0 - 1 ], 
    	  τ̂^x ≡1/c[ 0 ω 1; ω 0 1; 1 1 0 ],

with c = (ω + √(8 + ω^2))/2, which is a kind of the Δ-type system <cit.>. 

In this paper, we employ the common sets of parameters in both quantum Wajnflasz–Pick model and the conventional spin-1/2 model, including the coupling strength J_ij, the magnetic fields h_i^z,x, and the annealing time T. By using these parameters, we can obtain the same spin configuration (+1 or -1) in the ground state of the problem Hamiltonian. We thus compare efficiency of these models from the success probability.





§ SCHRÖDINGER DYNAMICS
 

In order to numerically calculate the success probability of the quantum annealing, 
we employ the Crank–Nicholson method <cit.> for solving the Schrödinger equation 

    i d/dt | Ψ (t) ⟩ = Ĥ (t) | Ψ (t) ⟩.

In this method, the time-evolution of the wavefunction is calculated by using the Cayley's form <cit.> 

    | Ψ (t + Δ t) ⟩ = 
    	1 - i ĤΔ t/2/1 + i ĤΔ t/2  | Ψ (t) ⟩.
 
Although the inverse matrix is needed, this method conserves the norm of the wave-function and is second-order accurate in time <cit.>. 

We first consider the fully connected model, where the spin-spin coupling is ferromagnetic and the longitudinal magnetic field is uniform h_i^z ≡ h, which is consistent with the earlier work <cit.>. 
For example, in the case where (ω, h) = (0.8,0.02) and (-0.8,-0.02) for (g_ u, g_ l) = (2,1), 
the time-dependence of the ground state population of the problem Hamiltonian, given by n_0 ≡ | ⟨Ψ (t) | Ψ_0 (T) ⟩ |^2, clearly shows that this quantity in the quantum Wajnflasz–Pick model is greater than that in the conventional spin-1/2 model (Panels (a) and (b) in Fig. <ref>). 
Here, |Ψ_0 (T) ⟩ is the ground state of the problem Hamiltonian, and | Ψ (t) ⟩ is the wave function obtained from the time-dependent Schrödinger equation. 
In the case where (ω, h) = (0.8,-0.1) and (-0.8,0.1) for (g_ u, g_ l) = (2,1), on the other hand, the ground state population of the problem Hamiltonian in the quantum Wajnflasz–Pick model is less than that in the spin-1/2 model (Panels (c) and (d) in Fig. <ref>).  

 

Compare the success probability of the quantum Wajnflasz–Pick model, P ≡ | ⟨Ψ (T) | Ψ_0 (T) ⟩ |^2, with that of the conventional spin-1/2 model denoted as P_1/2, 
where |Ψ (T) ⟩ is the final state obtained from the time-dependent Schrödinger equation. 
In almost all regions in the ω-h plane, efficiencies of both models are almost the same, where the ratio of the success probability of the quantum Wajnflasz–Pick model and that of the conventional spin-1/2 model is almost unity (Fig. <ref>). 
On the other hand, in the regime of the weak longitudinal magnetic field h, we can find higher or lower efficiency regions in the quantum Wajnflasz–Pick model, compared with the spin-1/2 model. 
In the spin glass model, a non-trivial state may emerge in the weak longitudinal magnetic field limit <cit.>. 
In a p-spin model where p=3,5,7, ⋯, the energy gap is known to close exponentially and the first-order phase transition emerges in the absence of the longitudinal magnetic field <cit.>. 
In this sense, it is of interest that the quantum Wajnflasz–Pick model may provide the high efficiency in the weak longitudinal magnetic field region. 

 

In the case where (g_ u, g_ l) = (2,2), where the numbers of upper and lower states are equal, 
the success probability of the quantum Wajnflasz–Pick model is almost equal to that of the conventional spin-1/2 model (Panel (a) in Fig. <ref>). 
In the case where (g_ u, g_ l) = (3,2), 
the success probability of the quantum Wajnflasz–Pick model is almost equal to that of the case where (g_ u, g_ l) = (2,1), 
where the differences between the number of the upper states and that of lower states are the same in both cases (Fig. <ref> and Panel (b) in Fig. <ref>). 

 



§ EIGENVALUES



Eigenvalue spectrum of the instantaneous Hamiltonian may help to understand these higher or lower success probabilities of the quantum Wajnflasz–Pick model than that of spin-1/2 model, although eigenvalues of the instantaneous Hamiltonian shows tangled spaghetti structures (Fig. <ref>). 
For example, in the case where (ω, h) = (0.8, -0.1), the energy gap between the ground state and the first excited state clearly closes once, which causes the low success probability (Panel (c) in Fig. <ref>). 
In the case where (ω, h) = (0.8, 0.02), the ground state and the first excited state are finally merged at the annealing time, where the degeneracy would cause the high success probability (Panel (a) in Fig. <ref>). 
However, according to the following discussion, it will be found that the latter explanation would not be correct in the case where (ω, h) = (0.8, 0.02). 
From panels (b) and (d) in Fig. <ref>, many crossings of eigenvalues are found to emerge. It suggests that there are no matrix elements in some states, and we may find symmetry behind the present quantum Wajnflasz–Pick model, where the Hamiltonian would be block diagonalized by a unitary operator Û. Since the energy spectrum of the original quantum Wajnflasz-Pick model shows very complicated behavior, it would be better to find out the reason of the high/low success probability from the reduced Hamiltonian, which are truly relevant for the efficiency of the quantum annealing. 


For example, in the case where (g_ u, g_ l) = (2,1), 
the single-spin Hamiltonian in the quantum Wajnflasz–Pick model is decomposable, where the irreducible representation is given by 

    Û^-1Ĥ(s) Û = 
    	[      - h^+ (s)              0 - 2√(2) h' (s);              0      - h^- (s)              0; - 2√(2) h' (s)              0          h^z s ]	,
 
for arbitrary values of s, 
by using the unitary operator 

    Û = [   1/√(2)   1/√(2)        0;   1/√(2) - 1/√(2)        0;        0        0        1 ],

where h^± (s) ≡ h^z s ± 2 ω h' (s), and h' (s) ≡ (1-s)h^x/(2c). 
As a result, we may reduce a quantum annealing problem in the single-spin quantum Wajnflasz–Pick model into that of the spin-1/2 model, the Hamiltonian of which is given in the form 

    ℋ̂ (s) = - [h^z s + ω h'(s) ] σ̂^z - 2 √(2) h'(s) σ̂^x - ω h'(s).

Since the initial ground state of the single-spin Hamiltonian is given by | Ψ (s=0) ⟩∝  (c/2, c/2, 1)^ T in the original quantum Wajnflasz–Pick model, 
this state can be mapped to Û |Ψ (s=0) ⟩∝ (c/√(2), 0, 1)^ T. 
It indicates that the initial ground state Û |Ψ (s=0) ⟩ can be also projected to the Hilbert space of the reduced Hamiltonian ℋ̂ (s). 

 

This reduction of the single-spin problem in the case where (g_ u, g_ l) = (2,1) can be generalized to an interacting N-spin problem (Fig. <ref>). A quantum annealing problem of the original quantum Wajnflasz–Pick model is reduced into that of the spin-1/2 model, given in the form 

    ℋ̂ (s) =     s  ( - ∑_i<j J_ijσ_i^z σ_j^z  ) 
    	- ∑_i h_ eff, i^z (s) σ_i^z 	
    	
        
    	- ∑_i h_ eff, i^x (s) σ_i^x
    	- ∑_i ω h_i' (s),

where 

    h_ eff, i^z (s) ≡    h_i^z s + ω h'_i (s) , 
    	
     
    	h_ eff, i^x (s) ≡    2√(2) h_i' (s) ,

with

    h_i' (s)	≡   (1-s) h_i^x/2 c.


As in the single-spin case, the initial ground state of the original N-spin quantum Wajnflasz–Pick model can be also projected to the Hilbert space of the reduced Hamiltonian (<ref>). 
The coupling J_ij in the reduced Hamiltonian is the same as that of the original Wajnflasz–Pick model. 
The effective longitudinal magnetic field h_ eff, i^z in the reduced Hamiltonian also reaches the same value as that of the original Wajnflasz–Pick model at the end of the annealing: h_ eff, i^z (s=1) = h_i^z. 
Eigenvalues of the reduced spin-1/2 model exactly trace eigenvalues in the original Wajnflasz–Pick model (Fig. <ref>). 
The time-dependence of the ground state population of the problem Hamiltonian is confirmed to show the completely same behavior between the reduced model and the original model. 



 

This effective model clearly explains behavior of success probability of the quantum Wajnflasz–Pick model shown in Fig. <ref>. 
Note that the coefficient c is a positive real number such that the maximum eigenvalue of τ^x is unity, and we take h_i^x = 1. 
Then, h_i'(s) ≥ 0 always holds during the annealing time 0 ≤ s ≤ 1. 
In the case where the longitudinal magnetic field h_i^z is very large, |h_i^z | ≫ |ω| h_i' (0), 
the effect of the original longitudinal magnetic field h_i^z is dominant compared with the effective additional term ω h'_i (s) except at the very early stage of the annealing s ≪ |ω h_i'(0)/h_i^z|. 
In this case, the problem Hamiltonian in the reduced model is almost the same as that in the conventional spin-1/2 model in Eq. (<ref>). As a result, the success probability of the quantum Wajnflasz–Pick model is almost the same as that of the conventional spin-1/2 model, which provides P ≃ P_1/2. 

In the case where the original longitudinal magnetic field h_i^z is not large, the effective additional longitudinal magnetic field ω h_i'(s) cannot be neglected compared with h_i^z. 
When the effective additional field is in the same direction as the original longitudinal field, 
the total effective longitudinal magnetic field h_ eff, i^z (s) is enhanced, which opens the energy gap between the ground state and the first excited state (Panels (a) and (b) in Fig. <ref>). 
This region is given by the condition ω h_i^z > 0, which is consistent with the result shown in Fig. <ref>. 
As a result, the success probability of the quantum Wajnflasz–Pick model become superior to that of the conventional spin-1/2 model. 
When the effective additional field is in the opposite direction to the original longitudinal field, 
the total effective longitudinal magnetic field h_ eff, i^z (s) is diminished, which closes the energy gap between the ground state and the first excited state (Panels (c) and (d) in Fig. <ref>). 
This region is given by the condition ω h_i^z < 0, which is consistent with the result shown in Fig. <ref>. 
As a result, the success probability of the quantum Wajnflasz–Pick model become inferior to that of the conventional spin-1/2 model. 

 

Behavior of success probability is also explained by the reference of the annealing time <cit.>

    𝒯≡ max_s  [ b(s)/Δ (s)^2 ],

where

    b(s) ≡    | ⟨Ψ_1 (s) | d Ĥ (s)/d s   | Ψ_0 (s) ⟩ | , 
    	
    Δ (s) ≡    E_1 (s) - E_0 (s).

Here, | Ψ_0(1) (s) ⟩ and E_0(1) (s) are the wave functions and eigenenergies of the ground (first-excited) state with respect to the instantaneous Hamiltonian, respectively. 
Annealing machine needs the annealing time T much larger than 𝒯. 
Let T^* ≡ b(s) /Δ^2(s) be an instantaneous reference time of the annealing. 
The maximum value of this time T^* in the reduced Wajnflasz–Pick model given in (<ref>) is suppressed compared with that of the conventional spin-1/2 model, 
where the effective additional field ω h'_i (s) is in the same direction as the original longitudinal field h_i^z (Panels (a) and (b) in Fig. <ref>). 
It is consistent with the case where the quantum Wajnflasz–Pick model is more efficient than the conventional spin-1/2 model in the region where ω h_i^z > 0 (Fig. <ref>). 
The maximum value of T^* in the effective Wajnflasz–Pick model has larger values than that of the spin-1/2 model, 
where the effective additional field ω h'_i (s) is in the opposite direction to the original longitudinal field h_i^z (Panels (c) and (d) in Fig. <ref>). 
It is consistent with the case where the quantum Wajnflasz–Pick model is less efficient than the conventional spin-1/2 model in the region where ω h_i^z < 0 (Fig. <ref>). 


 


In order to perform the scaling analysis of the minimum energy gap Δ_ min≡ min [E_1  (s) - E_0(s) ], we consider the p-spin model in the absence of the longitudinal magnetic field: 

    Ĥ(s) = s  ( - 1/N^p-1∑_i_1, ⋯, i_p ^N τ̂_i_1^z  ⋯τ̂_i_p^z  ) + (1-s)  ( -h^x ∑_i^N  τ̂_i^x  ),

where the transverse magnetic field is homogeneous. 
Replacement of τ_i^x,y with σ_i^x,y provides the conventional p-spin model, where the first order phase transition emerges, and the minimum energy gap is known to close exponentially as N increases in the case where p is odd <cit.>. 
After mapping to the subspace spanned by the spin-1/2 model, the reduced Hamiltonian of the quantum Wajnflasz–Pick model with (g_ u, g_ l) = (2,1) can be reduced to 

    ℋ̂ (s) =     - s1/N^p-1∑_i_1, ⋯, i_p ^N σ̂_i_1^z  ⋯σ̂_i_p^z 
    - (1-s) Γ^z ∑_i^N  σ̂_i^z 
    
        - (1-s) Γ^x ∑_i^N  σ̂_i^x , 
    
     
    =      -s  1/N^p-1 ( M̂^z )^p 
    - (1-s)   Γ^z  M̂^z 
    - (1-s)  Γ^x M̂^x ,

up to the constant energy shift, where Γ^z ≡ω h^x / (2 c), Γ^x ≡√(2) h^x / c, and M̂^z, x≡∑_i^N σ̂_i^z,x. 
By using the commutation relation [σ̂_i^x, σ̂_j^z] = 2 i σ̂_i^z δ_ij and by following the standard argument of the angular momentum, where the total spin M̂^2 ≡ (M̂^x)^2 +  (M̂^y)^2 +  (M̂^z)^2 conserves, 
the Hilbert space can be spanned by states | J, M⟩, where M̂^2 |J, M⟩ = J (J+2) | J, M ⟩ and M̂^z | J, M ⟩ = M | J, M ⟩ with M = -J, -J + 2, ⋯, J -2 , J. The diagonal elements of this Hamiltonian is given by ℋ_MM = - sM^p/(N^p-1) - (1-s)Γ^z M, and the off-diagonal elements are ℋ_M,M± 2 = - (1-s)Γ^x √(J(J+2) - M (M± 2))/2. Since the ground state of this model is given by the case J = N, we diagonalize the (N+1) × (N+1) matrix of the reduced Hamiltonian. 
We compare the minimum energy gap of this model reduced from the quantum Wajnflasz–Pick model with that of the conventional p-spin model composed of the spin-1/2 system (Eq. (<ref>) with Γ^z = 0 and Γ^x = h^x). 
Figure <ref> clearly shows that the minimum energy gap closes exponentially in the conventional spin-1/2 model, and the gap closes polynomially in the model reduced from the quantum Wajnflasz–Pick model. This polynomial gap closing originates from the emergence of the effective longitudinal magnetic field in the reduced model: Γ^z = ω h^x / (2c) ≠ 0. 


 



§ RANDOM COUPLING


In the random spin-spin coupling case, where J_ij are randomly generated by the gaussian distribution function <cit.> 

    P(J_ij) = √(N2 π)exp ( - N^2 J_ij^2 ),

the density plot of the mean-value of the success probability is similar to the uniform coupling case. 
The maximum (minimum) value of the success probability is, however, suppressed (increased) compared with the uniform coupling case (Fig. <ref>). 
The variances of the success probability of the quantum Wajnflasz–Pick model are almost ranged from 0.03 to 0.06 in the first and third orthants in the ω-h plane, where the higher success probability may be obtained than the conventional spin-1/2 model. 
They are almost ranged from 0.02 to 0.15 in the second and forth orthants in the ω-h plane, where the lower success probability may be obtained. 
In the spin-1/2 model, the variance of the success probability is almost within the range from 0.03 to 0.06 in all the orthants.


 

The discussion above is in the case for a uniform longitudinal magnetic field. 
In the following, we discuss the case of random longitudinal magnetic fields h_i^z in addition to the random interactions J_ij.   
The success probabilities P and P_1/2 are almost equal in the weak internal state coupling case (ω = ± 0.1 in Fig. <ref>). 
In the strong internal state coupling case (ω = ± 1 in Fig. <ref>), the distribution is broaden. 
Although we can find cases where the conventional spin-1/2 model is superior to the quantum Wajnflasz–Pick model, 
we can also find many cases where the quantum Wajnflasz–Pick model is superior to the conventional spin-1/2 model, where the success probability is close to the unity compared with the conventional spin-1/2 model. 

  

In these random coupling cases, 
it may not be definitely concluded that the quantum Wajnflasz–Pick model is always more efficient than the conventional spin-1/2 model. 
The variance is relatively large, and there are cases where the quantum Wajnflasz–Pick model is inferior to the conventional spin-1/2 model (Fig. <ref>). 
However, we can find many cases where the quantum Wajnflasz–Pick model is possibly more efficient than the conventional spin-1/2 model. 
In the quantum Wajnflasz–Pick model and its reduced model, we have chances to find a better solution of the combinatorial optimization problem. 
In real annealing machines, we can extract a better solution after performing many sampling experiments by tuning ω. 





§ DISCUSSION


In the case where (g_ u, g_ l) = (2,1), the spin matrix in the quantum Wajnflasz–Pick model is represented by a (3×3)-matrix, which suggests that the quantum Wajnflasz–Pick model in this case may be mapped into the model represented by the spin-1 matrices given by 

    Ŝ^x = 1/√(2)[ 0 1 0; 1 0 1; 0 1 0 ], 
    Ŝ^y = i/√(2)[  0 -1  0;  1  0 -1;  0  1  0 ], 
    Ŝ^z =                        [  1  0  0;  0  0  0;  0  0 -1 ].
 
Indeed, after we interchange elements of second and third rows in the spin matrices defined in Eq. (<ref>) in the case where (g_ u, g_ l) = (2,1), as well as we interchange elements of second and third columns, simultaneously, we find the following maps  

    τ̂^z ↦    q̂^z ≡2/√(3)Q̂^3z^2 -r^2 + 1/3,
    
    τ̂^x ↦    q̂^x ≡1c [ √(2)Ŝ^x + ωQ̂^x^2-y^2 - ωQ̂^xy],

where we have introduced quadrupolar operators <cit.>

    Q̂^3z^2 -r^2≡   1/√(3) [2 (Ŝ^z)^2 - (Ŝ^x)^2 - (Ŝ^y)^2], 
    
    Q̂^x^2-y^2≡    (Ŝ^x)^2 - (Ŝ^y)^2, 
    
    Q̂^xy≡   Ŝ^x Ŝ^y + Ŝ^y Ŝ^x ,

and ω (ω) is the real (imaginary) part of ω. 
Since [q̂^z, (Ŝ^x)^2] = 0 and [q̂^x, (Ŝ^x)^2] = i (ω/c) Ŝ^x hold, we find that (Ŝ^x)^2 is the operator of the conserved quantity in the case where the parameter ω is a real number. 
The coupling of τ̂_i^z τ̂_j(≠ i)^z is mapped into the interaction q̂_i^zq̂_j(≠ i)^z, which is a kind of the biquadratic interaction with respect to the spin. 
In short, the interacting quantum Wajnflasz–Pick model with (g_ u, g_ l) = (2,1) can be mapped into the spin-1 model with an artificial biquadratic interaction. In particular, in the case where ω∈ℝ, there is the hidden symmetry related to (Ŝ^x)^2, which indicates that the quantum Wajnflasz–Pick model is reducible in this case. 



It is general that an interacting quantum Wajnflasz–Pick model is reducible to the conventional spin-1/2 model. 
It holds for an arbitrary number of the degeneracy (g_ u, g_ l) and at an arbitrary time s, which can be proven in the case where the parameter ω is a real number and the condition ω > -1 holds. 
In Supplementary Information, we show that the Hamiltonian of the interacting quantum Wajnflasz–Pick model with arbitrary (g_ u, g_ l) can be projected to the spin-1/2 model, and the initial ground state in the original quantum Wajnflasz–Pick Hamiltonian is also projected to the reduced Hilbert space. 
It indicates that the quantum annealing in the quantum Wajnflasz–Pick model can be always described by the reduced Hamiltonian. 

As shown in Supplementary Information, this projection holds not only in the 2-body interacting quantum Wajnflasz–Pick model, 
but also in the N-body interacting model. 
It indicates that if the quantum Wajnflasz–Pick model is embedded into the Lechner–Hauke–Zoller (LHZ) architecture <cit.>, 
it can be also projected into the LHZ architecture composed of the spin-1/2 model, where the effective additional magnetic fields may emerge. 
The present quantum Wajnflasz–Pick model is a degenerate two-level system in the presence of the transverse magnetic field. 
The possibility of the implementation of  the degenerate two-level system has been discussed for the D_2 line of ^87Rb <cit.>. 
The quantum Wajnflasz–Pick model is also similar to the Δ-type cyclic artificial atom in the superconducting circuit <cit.>. 
In the Δ-type artificial atom, the population is controllable by making use of the amplitudes and/or phases of microwave pulses, 
where the amplitudes alone controls the population in the conventional three-level system (Λ-type system) <cit.>. 
However, the Δ-type system in the superconducting circuit is not an exactly degenerate two-level system. 
With this regard, it may be difficult to directly implement our model in the Δ-type cyclic artificial atom in the superconducting circuit. 
Actually, it may be feasible to employ the spin-1/2 model with the scheduling function inspired by the quantum Wajnflasz–Pick model, in the case where the Schrödinger dynamics without the dissipation holds. 


The quantum Wajnflasz–Pick model is one of the qudit models, which is a kind of the artificial Δ-type system <cit.> in the case where (g_ u, g_ l) = (2,1). 
The question naturally arises whether the Λ-type system also shows the higher success probability than the conventional spin-1/2 model. 
The spin matrix of the Λ-type system we employ here is given by 

    τ̂^z = [ 0 0 0; 0 1 0; 0 0 ε ], 
    τ̂^x = 1/c[ 0 κ 0; κ 0 1; 0 1 0 ],

where we take |ε| ≤ 1, and the coefficient c ≡√(1+κ^2) is a normalization factor so as the maximum eigenvalues of τ̂^x,z are unity. 
The Hamiltonian of the quantum annealing with the Λ-type system is given by Eqs. (<ref>), (<ref>), and (<ref>), where τ̂^x,z are replaced with those given in (<ref>). 
The success probability in the Λ-type system is found to be higher than that in the conventional spin-1/2 model, in the case where ε is small in the weak longitudinal magnetic field region, which is similar to the case of the quantum Wajnflasz–Pick model (Panels (a) and (b) in Fig. <ref>). 
When ϵ is large, on the other hand, the success probability is drastically suppressed (Panel (c) in Fig. <ref>). 
In the case of a single Λ-spin system with ϵ = 0, which corresponds to a degenerate two-level system, 
the unitary transformation 

    Û = 1/c[  κ  0  1;  0  1  0;  1  0 -κ ]
 
can map the Hamiltonian Ĥ (s) = - s h^z τ̂^z - (1-s) h^x τ̂^x to the following block diagonal form: 

    Û^-1Ĥ (s) Û = [           0 - (1-s) h^x           0; - (1-s) h^x     - s h^z           0;           0           0           0 ].

As a result, after exchanging the first and second columns and also the first and second rows, we may reduce a quantum annealing problem in this Λ-spin model into that of the spin-1/2 model, the Hamiltonian of which is given by ℋ̂ (s) = - s h^z σ^z/2 - (1-s)h^x σ^x - sh^z/2. 
Although the Λ-type system may provide the higher success probability than the conventional spin-1/2 model, the effect of dark states (never employed states) on the quantum annealing in the general Λ-spin case and its reduction to the spin-1/2 model in the many-spin system would be important issues for future study. 

To summarize, we have demonstrated that qudit models, such as the quantum Wajnflasz–Pick model as well as the Λ-type system, may provide the higher success probability than the conventional spin-1/2 model in the weak magnetic field region. 
We have analytically shown that the quantum Wajnflasz–Pick model can be reduced into the spin-1/2 model, where effect of the transverse magnetic field in the original Hamiltonian emerges as the effective additional longitudinal magnetic field in the reduced Hamiltonian, which possibly opens the energy gap between the ground state and the first excited state in the reduced Hamiltonian. 
Since qubits have experimental advantages for the manipulation, the direct implementation of the reduced spin-1/2 model may be convenient for the quantum annealing. 
On the other hand, the reduction to the subspace in terms of the spin-1/2 model is useful only in the case where we focus on the Schrödinger dynamics. If we consider the dissipation as a realistic system, the transition between the subspaces emerges. The efficiency of the quantum annealing in this system is open for further study. 




  




§ CONCLUSIONS

We studied the performance of the quantum annealing constructed by one of the degenerate two-level systems, called the quantum Wajnflasz–Pick model. 
This model shows the higher success probability than the conventional spin-1/2 model in the region where the longitudinal magnetic field is weak. 
The physics behind this is that the quantum annealing of this model can be reduced into that of the spin-1/2 model, 
where the effective longitudinal magnetic field in the reduced Hamiltonian may open the energy gap between the ground state and the first excited state, which gives rise to the suppression of the Landau–Zener transition. 
The reduction of the quantum Wajnflasz–Pick model to the spin-1/2 model is general at an arbitrary time as well as in an arbitrary number of degeneracies. 
We also demonstrated that the Λ-type system also shows the higher success probability than the conventional spin-1/2 model in the weak magnetic field regions. 
We hope that studying quantum annealing with variant spins, and utilizing the insight of their reduced model will promote further development of high performance quantum annealer. 



§ ACKNOWLEDGEMENT

We thank R. van Bijnen, W. Lechner, Y. Matsuzaki, T. Ishikawa, T. Yamamoto, and T. Nikuni for fruitful discussions and comments. 
Two of the authors (S.W. and S.K.) were supported by Nanotech CUPAL, Japan Science and Technology Agency (JST). 
Y.S. and S.K. were supported by the New Energy and Industrial Technology Development Organization (NEDO), Japan. 












§ SUPPLEMENTAL INFORMATION


We have shown in (<ref>) that the quantum Wajnflasz–Pick model with the N spins with (g_ u , g_ l) = (2,1) can be reduced into the spin-1/2 model. In the single-spin case, in particular, 
if we take 

    |ϕ_u⟩_   = 1/√(2) (1, 1, 0)^ T, 
    |ϕ_l⟩_   = (0,0,1)^ T,
 
the Hamiltonian (<ref>) projected into the Hilbert space spanned by |ϕ_u,l⟩_ is represented by 

    ℋ̂ (s) =    [ ⟨ϕ_ u|Ĥ(s) |ϕ_ u⟩ ⟨ϕ_ u|Ĥ(s) |ϕ_ l⟩; ⟨ϕ_ l|Ĥ(s) |ϕ_ u⟩ ⟨ϕ_ l|Ĥ(s) |ϕ_ l⟩ ]
     
        =    [ - h^z s - 2 ω h' (s)       - 2√(2) h' (s);       - 2√(2) h' (s)                h^z s ].
 
It can be clearly found that this representation is exactly the same form as the block matrix shown in (<ref>).

In this Supplementary Information, by generalizing this idea, we show that the quantum annealing problem of the quantum Wajnflasz–Pick model with the N-spins with arbitrary number of degeneracy g_ u,l can be reduced into the spin-1/2 model. 
First, consider the Hamiltonian of the quantum Wajnflasz–Pick model 

    Ĥ(s)    = s Ĥ_z + (1-s) Ĥ_x,

where Ĥ_x ≡  - ∑_i=1^N h_i^x τ̂_i^x with h_i^x > 0, and Ĥ_z ≡ f(τ̂_1^z, … ,τ̂_N^z) can be expanded in the Maclaurin series. 
Equation (<ref>) is a generalization of (<ref>) with (<ref>) and (<ref>). 
We here introduce eigenstates of  a single spin τ̂_i^z at a site i as 

    |u_1⟩_i, |u_2⟩_i, … , |u_g_u⟩_i, 
    |l_1⟩_i, |l_2⟩_i, … , |l_g_l⟩_i,

where |u_k⟩_i for k = 1, 2, ⋯, g_ u and  |l_k⟩_i for k = 1, 2, ⋯, g_ l are eigenstates whose eigenvalues of τ̂_i^z is +1 and -1, respectively. 

In the following, we first prove a lemma I:  if the parameter ω is a real number, the Hamiltonian of the N-spin quantum Wajnflasz–Pick model can be decomposed into two parts 

    Ĥ = P̂ĤP̂ + (1̂ - P̂)Ĥ(1̂ - P̂),

where P̂≡⊗_i=1^NP̂_i with P̂_i = |ϕ_u⟩_i⟨ϕ_u|_i + |ϕ_l⟩_i⟨ϕ_l|_i 
is a projection operator. A local projection operator P̂_i is spanned by two bases |ϕ_u,l⟩_i, where 

    |ϕ_u⟩_i   ≡1/√(g_u)∑_k=1^g_u|u_k⟩_i, 
    |ϕ_l⟩_i   ≡1/√(g_l)∑_k=1^g_l|l_k⟩_i.
 
It indicates that the Hilbert space of the quantum Wajnflasz–Pick model can be reduced to a subspace spanned by |ϕ_u,l⟩_i. 
We also prove a lemma II: if the parameter ω is a real number and the condition ω > -1 holds, 
the ground state of the initial Hamiltonian Ĥ_x with h_i^x > 0 is an element of the Hilbert space spanned by |ϕ_u,l⟩_i. 
According to these two lemmas I and II, in the case where ω∈ℝ and ω > -1, the quantum annealing problem in the quantum Wajnflasz–Pick model is represented as a model where the local spin has two states—the spin-1/2 model. 

We first consider the lemma I. Since P̂^2 = P̂, a necessary and sufficient condition providing (<ref>) is given by 

    [P̂, Ĥ] = 0.
 
The condition (<ref>) can be reduced into 

    [ P̂, Ĥ]
           =
        s [ P̂, Ĥ_z] + (1-s) [ P̂, Ĥ_x] = 0.

Here, we will easily prove that [ P̂, Ĥ_z ]  = 0, for the projection operator P̂ is composed of bases that diagonalize Ĥ_z. 
Indeed, since Ĥ_z is composed of τ̂_i^z, what we need to show is 

    [P̂_i, τ̂_i^z]= 0.

A spectral representation of the single-spin operator τ̂_i^z can be represented by eigenstates of τ̂_i^z, given in the form 

    τ̂_i^z   =
        ∑_k=1^g_u|u_k⟩_i⟨u_k|_i
        - ∑_k=1^g_l|l_k⟩_i⟨l_k|_i.

The projection operator P̂_i is also composed of eigenstates of τ̂_i^z. 
We can thus immediately conclude that (<ref>) holds, which provides [ P̂, Ĥ_z ]  = 0. 
The result (<ref>) can also provide the following representation 

    τ̂_i^z   = P̂_iτ̂_i^zP̂_i
                             + (1̂_i - P̂_i)τ̂_i^z(1̂_i - P̂_i).


The remain we need to prove is 

    [ P̂ , Ĥ_x]
           =
        - ∑_j=1^N h_j^x [ ⊗_i=1^NP̂_i, τ̂_j^x] =0 .

The necessary and sufficient condition for (<ref>) for arbitrary h_j^x is 

    [P̂_i, τ̂_i^x] = 0,

because we can expand a term in (<ref>) in the following way 

    [ ⊗_i=1^NP̂_i, τ̂_j^x]
           =
        (⊗_i=1^j-1P̂_i)
        [P̂_j, τ̂_j^x]
        (⊗_i=j+1^NP̂_i) .

In order to show (<ref>), it is convenient to introduce the spectral representation of the single-spin operator τ̂^x_i, given by 

    τ̂_i^x   =
        1/c ( ωÂ_i + B̂_i +  H.c. ) ,

where 

    Â_i ≡   ∑_k,k'=1
    k > k'^g_u|u_k'⟩_i⟨u_k|_i + ∑_k,k'=1
    k > k'^g_l|l_k'⟩_i⟨l_k|_i, 
    
    B̂_i ≡   ∑_k=1^g_u∑_k'=1^g_l|u_k⟩_i⟨l_k'|_i.
 
Here, a constant c is the normalization factor such that the spectral norm of τ̂_i^x is to be unity. 
We can also represent τ̂_i^x as 

    τ̂_i^x   =
        1/c [ 
            1/2ω(
                Â_i^ u + Â_i^ l)
            + iωÂ_i + B̂_i' +   H.c. ]

where

    Â_i^ u≡    g_u|ϕ_u⟩_i⟨ϕ_u|_i
                - ∑_k=1^g_u|u_k⟩_i⟨u_k|_i, 
    
    Â_i^ l≡    g_l|ϕ_l⟩_i⟨ϕ_l|_i
                - ∑_k=1^g_l|l_k⟩_i⟨l_k|_i , 
    
    B̂_i' ≡   √(g_ug_l)|ϕ_u⟩_i⟨ϕ_l|_i .

Here, ω and ω in (<ref>) are the real and imaginary parts of ω, respectively. 
By using the representation (<ref>), we can obtain the following result: 

    [ P̂_i, τ̂_i^x]
           =
        [|ϕ_u⟩_i⟨ϕ_u|_i, τ̂_i^x]
        + [|ϕ_l⟩_i⟨ϕ_l|_i, τ̂_i^x]
        
       =
        iω (Ĉ_i^ u + Ĉ_i^ l +  H.c.),

where 

    Ĉ_i^ u≡   1/c√(g_u)∑_k=1^g_u(2k- g_u - 1)
               |ϕ_u⟩_i⟨u_k|_i , 
        
    Ĉ_i^ l≡   1/c√(g_l)∑_k=1^g_l(2k- g_l - 1)
           |ϕ_l⟩_i⟨l_k|_i .

From the result (<ref>), we find that (<ref>) holds in the case where ω is a real number: ω = 0, 
which provides 

    τ̂_i^x   = P̂_iτ̂_i^xP̂_i
                             + (1̂_i - P̂_i)τ̂_i^x(1̂_i - P̂_i).

As a result, (<ref>) is found to be hold, and the Hamiltonian Ĥ are reducible and block diagonalizable, independent of the time s as well as a structure of the spin coupling. 

Finally, we will prove the lemma II, where the ground state of the initial Hamiltonian Ĥ_x with h_i^x > 0 is an element of the Hilbert space spanned by |ϕ_u,l⟩_i, if the conditions ω∈ℝ and ω > -1 hold. 
In the following, we assume that the parameter ω is a real number. 
Since the initial driver Hamiltonian Ĥ_x is a sum of a single-site spin operator -h_i^xτ̂_i^x with h_i^x > 0, 
let |Ψ (s=0) ⟩≡⊗_i=1^N|ψ_0⟩_i be the initial ground state, where |ψ_0⟩_i is the ground state of - h_i^x τ̂_i^x with h_i^x > 0. 
In order to prove the lemma II, 
it is sufficient to show that the state |ψ_0⟩_i is an element of the Hilbert space spanned by |ϕ_u,l⟩_i. 

We construct eigenstates of - τ̂_i^x, whose number is  (g_ u + g_ l), given in the form 

    |m_u⟩_i   ≡1/√(g_u)∑_k=1^g_u
        e^2π i(k-1)m_u / g_u|u_k⟩_i
    |m_l⟩_i   ≡1/√(g_l)∑_k=1^g_l
        e^2π i(k-1)m_l / g_l|l_k⟩_i
    |λ_±⟩_i   ≡√(g_u) a_±|ϕ_u⟩_i
                            +√(g_l)|ϕ_l⟩_i,

where m_u,l = 1, 2, …, g_u,l-1. 
Eigenvalues of -τ̂_i^x for |m_u,l⟩_i are given by ω/c. 
The states |λ_±⟩_i become eigenstates of -τ̂_i^x, if we take 

    a_±≡(g_u - g_l)ω∓√((g_u - g_l)^2ω^2
                                  + 4g_ug_l)/2g_u,

whose eigenvalues of -τ̂_i^x are given by 

    λ_± = 1/c{(1-g_u+g_u/2)ω±1/2√((g_u - g_l)^2ω^2
                                  + 4g_ug_l)}.

These eigenstates |m_u,l⟩_i and |λ_±⟩_i are orthogonal. 
We can find that the relations λ_+ > λ_- as well as (ω/c) > λ_- hold in the case where ω > -1. 
As a result, h_i^x λ_- is the minimum eigenvalue of - h_i^x τ̂_i^x with h_i^x > 0, and the ground state is |λ_-⟩_i = √(g_u) a_-|ϕ_u⟩_i +√(g_l)|ϕ_l⟩_i, 
which indicates that the initial ground state is an element of the Hilbert space spanned by |ϕ_u,l⟩_i. 

To summarize, in the case where ω is a real number and ω > -1 holds, 
the quantum annealing problem
 in the quantum Wajnflasz–Pick model can be exactly described by the reduced Hilbert space spanned by |ϕ_u,l⟩_i. 

As in panel (b) in Fig. <ref>, 
we can find that the level crossing with respect to the ground state emerges twice while annealing.  
It might be expected as the emergence of the double first order phase transition while annealing discussed in Ref. <cit.>, 
where the system may come back to the ground state at the end of the annealing. 
However, there is no Landau–Zener tunneling between them, because we find no matrix elements between these level crossing states. 
In the case where ω≠ 0, non-zero value of matrix elements emerges between the Hilbert space projected by P̂ and their orthogonal complement, which provides the anti-crossing of energy levels. In this case, discussion of the quantum annealing will become more complicated than that in the present study. 
At non-zero temperature case, the Schrödinger dynamics employed in this paper is not applicable, 
and it will be important to consider lower energy states in the Hilbert space projected by P̂ as well as those in their orthogonal complement. 





apsrev4-1































































































































































































































































































































































































































































