Can adiabatic algorithms with extra items always be efficient in quantum computation?

Abstract

It has been known that when an assisted driving item is added to the Hamiltonian of the main system, the efficiency of the resultant adiabatic evolution can be significantly improved. In some special cases, it can be seen that, only by adding an assisted driving Hamiltonian can the resultant adiabatic evolution work. So it seems that, the additional driving Hamiltonian plays an important role in adiabatic computing. In this paper, we show five kinds of possible forms of the driving Hamiltonian, and analyses the performance of the algorithms. We find that the former fourth kinds of driving Hamiltonian may still cause the adiabatic algorithm lose their efficiency when the overlap of the initial and final states equals some special value. More importantly, we find that only the final kinds of the driving Hamiltonian can be extended. By modifying its interpolating functions, the final kind of adiabatic algorithm can suit any fidelity of the systems to keep the adiabatic evolution always be valid. Finally, the time complexity of the extended algorithm is better than the original adiabatic algorithm, which owns a constant running time complexity. Although the time complexity is shifted to the complexity of implementing the driving Hamiltonian added.

Keywords

Fidelity driving Hamiltonian adiabatic evolution interpolating functions

1 Introduction

Quantum adiabatic evolution has been developed as an alternative to traditional circuit model of quantum computation, which have some advantages especially like robustness against different kinds of perturbations, such as decohenrence, and unitary control errors, and it is believed to have the power to solving various kinds of NP problems. In addition, other researchers also have shown that AQC is equivalent to standard quantum computing. The essence of an adiabatic quantum algorithm is to prepare a quantum system in the ground state of a simple initial Hamiltonian, then slowly transform this Hamiltonian to a final Hamiltonian whose ground state encodes the solution to the problem which will be solved. Suppose the state of a quantum system is |φ (0)〉, which evolves according to the Schrödinger equation.

Adiabatic quantum computation (AQC) was originally proposed [1] as a possible means for solving NP problems faster than classical computation. The essence of AQC is that, the Hamiltonian of the system is evolved from an initial Hamiltonian H₁, whose ground state determines the initial state of the system. H₁ is then slowly transformed into the final Hamiltonian H₂, whose ground state is the solution to the problem. To ensure a large amplitude of the ground state at the end of the evolution, the computation time T should increase as $T \sim g_{min}^{2}$ , where g_min is the minimum energy gap between the ground state and the first excited state during the evolution. The complexity of AQC is therefore determined by the scaling of g_min with the problem size.

Since its proposal, the effectiveness of AQC for solving NP problems has been a subject of controversy. Suppose the state of a quantum system is |φ (t)〉, which evolves according to the Schrödinger equation. $i \frac{d}{dt} | φ (t) 〉 = H (t) | φ (t) 〉 .$ (1)

For the sake of convenience, the time-dependent Hamiltonian H (t) can be reparametrized as $H (s) = H (t / T), for 0 \leq s \leq 1 .$ (2)

Usually, the instantaneous Hamiltonian H (s) which connects the initial Hamiltonian H₁ and the final Hamiltonian H₂ of the quantum system is a linear adiabatic evolution path, as shown below: $H (s) = (1 - s) H_{1} + {sH}_{2}, for 0 \leq s \leq 1 .$ (3)

This adiabatic algorithm is efficient for solving a lot of convection problems. For example, the adiabatic evolution based quantum algorithms are widely used for solving various kinds of interesting problems, such as these shown in [2 –7]. Another important aspect of adiabatic computing is that adiabatic evolution is polynomial equivalent to the standard model of quantum computation, which was firstly discovered by Quiroz et al. [8]. Some subsequent works also have close relations with this important topic of quantum adiabatic computing [9, 10]. However, if the initial and final states are orthogonal, as stated by EDWARD et al. [11] and Farhi et al. [12], the traditional algorithm will be powerless. To resolve this problem, Peschina et al. [13] argue that there is no reason not to try the paths involving terms that are not linear combinations of the initial and final Hamiltonians. It has been found that the adiabatic algorithms with the adding assisted driving item can change the performance to turn an algorithm from failure to success of solving some special problems. Andrecut et al. [14] apply this method to the quantum search problem [15]. By a suitable choice of the time-dependent Hamiltonian, it is possible to do the calculation in constant time, independent of the number of items in the database. Usually, when a problem of interest is mapped to solve the ground state of a quantum system, there are a lot of ways to construct the initial Hamiltonian and the final Hamiltonian. These have led Peschina et al. [13] to show the exponential small gap discovered by Farhi et al. [12] when solving 3-SAT problems could be overcome by using different initial Hamiltonians, and Choi [16] to conjecture different reductions among NP-complete problems, which is likely to give rise to different final Hamiltonians, and thus different adiabatic quantum algorithms to which the arguments in the corresponding literature [17, 18] for the failure of the adiabatic quantum algorithms do not apply. Actually, all these researchers have done is modifying the structure of local Hamiltonian, which is the time-dependent Hamiltonian during the evolution when the initial Hamiltonian is switched to the final Hamiltonian in adiabatic quantum models, to improve the computation time complexity or avoiding failure in AQC.

It is known that a usual linear adiabatic quantum model will fail when the overlap between the initial Hamiltonian and final Hamilton equals zero [12]. In this paper, we will further investigate all possible forms of the assisted driving item in AQC. Some driving items will not be as beneficial as the general adiabatic algorithm, and it brings more complexity to construct the time-dependent Hamiltonian. Others are only efficient when the initial state has a zero overlap with the final state. Does there exist a general model which can be always success no matter what a fidelity the system owns? In response, we provide two strengthening conditions on evolution path of adiabatic quantum algorithm. In virtue of these strengthening conditions, the final adiabatic algorithm which owns a special extra items can be extended efficiently to avoid failure forever, whatever the overlap between the initial and final state gets, the adiabatic condition can be held to keep the evolution complete. Furthermore, the time complexity of the extensional algorithm has a better runtime complexity than the general liner adiabatic algorithm. But as what we have stated, the time complexity is shifted to the complexity of implementing the driving Hamiltonian added. The strengthening conditions can also detect whether there exists a break point to cause the failure of algorithm.

The remainder of the paper is organized as follows: insect. 2, we show different possible forms of the extra items in the nonlinear adiabatic algorithm, and summarize the performance of them. In Section 3, we introduce two reinforcing conditions from a general minimum energy gap of the fifth kind of adiabatic algorithm with a special extra item. With the help of these conditions, we extend the normal nonlinear model, and estimate the time complexity of the extended model. Then we determine a usual quantum adiabatic model with these strengthening conditions. In the last section, we summarize and draw some conclusions.

2 The different forms of assisted extra Hamiltonian

For convenience, suppose we want to evolve the initial state |φ₀〉 to a solution state denoted as |φ₁〉 of a quantum system by the widely used linear adiabatic evolution. Abstractly, the initial and final Hamiltonians of the quantum system can be simply encoded as: $H_{1} = I - | φ_{0} 〉〈 φ_{0} |, H_{2} = I - | φ_{1} 〉〈 φ_{1} | .$ (4)

For convenient calculation, on the basis of the Gram-Schmidt transformation, the initial and final states can be rewritten as: $| φ_{0} 〉 = | α 〉,$ (5) $| φ_{1} 〉 = α | α 〉 + b | β 〉,$ (6) where $a = 〈 φ_{0} | φ_{1} 〉, b = \sqrt{1 - a^{2}},$ (7) and |α〉, |β〉 are orthogonal bases in a two-dimensional Hibernate space. A is always called the fidelity between the initial and final states of the system. According to Equation (3), H (s) has the following matrix representation: $H (s) = (\begin{matrix} {sb}^{2} - sab \\ - sab 1 - {sb}^{2} \end{matrix}),$ (8) and we can easily obtain the minimal gap of the system as: $\underset{0 \leq s \leq 1}{g_{min}} = | E_{0} (s) - E_{1} (s) | = | a |,$ (9) where E₀ and E₁ are the two eigenvalues of matrix H (s). The time complexity for this algorithm is: $T \in O (a^{- 2}) .$ (10)

It is easy to know that if a equals zero, the running time will be infinite. As regards a normal nonlinear adiabatic model [13, 14] with the extra driving Hamiltonian, we consider the following Hamiltonian,

$\begin{matrix} \hat{H (s)} & = & f (s) H_{1} + g (s) H_{2} + h (s) H_{e}, \\ for 0 \leq s \leq 1 . \end{matrix}$ (11) where f (s), g (s), h (s) are arbitrary continuous functions with an independent variable s, and f (s), g (s), h (s) satisfy the initial conditions:

$\begin{matrix} h (0) & = & h (1) = 0, f (1) = g (0) = 1, \\ f (0) = g (1) = 1 . \end{matrix}$ (12)

It should be noted that, here and in the rest of the paper we will use f, g, h as the simplified versions of f (s), g (s), h (s). In the following part of this section, we will show five kinds of adiabatic algorithms with different extra Hamiltonian. The first three kinds of adiabatic algorithms will be proven to fail to complete the adiabatic evolution with any evolving interpolating functions when the overlap between the initial and final states equals zero. Although the fourth kind of adiabatic algorithm has solved the problem that the initial and final state has a zero overlap. However, it always owns a drawback to lead the adiabatic evolution fail when the overlap bigger enough than $\frac{\sqrt{2}}{2}$ . And the last kind of adiabatic algorithms seems be efficient under a special case. Therefore, the last one may be extended to suit any overlap of the system.

Firstly, we consider the driving item H_e = |φ₀ 〉〈 φ₀|, and by using Equation (11), the time-dependent Hamiltonian of the adiabatic system will be rewritten as:

$\begin{matrix} \hat{H (s)} & = & f (I - | φ_{0} 〉〈 φ_{0} |) + g (I - | φ_{1} 〉〈 φ_{1} |) \\ + h (| φ_{0} 〉〈 φ_{0} |), for 0 \leq s \leq 1 \end{matrix}$ (13)

With Equations (5–7), the Hamiltonian matrix will be set as: $\hat{H (s)} = (\begin{matrix} b^{2} g + h - abg \\ - abg f + a^{2} g \end{matrix}),$ (14) and we can easily work out the minimal gap of the system as:

$\begin{matrix} \underset{0 \leq s \leq 1}{g_{min}} & = & | E_{0} (s) - E_{1} (s) | \\ = & \sqrt{{(f - g + h)}^{2} + 4 a^{2} g (f - h)}, \end{matrix}$ (15)

When the overlap between φ₀〉 and φ₁〉 equals zero, the minimal gap is ${\underset{0 \leq s \leq 1}{g_{min}} |}_{a = 0} = | f - g + h |,$ (16)

We construct a new function F (s) = f - g + h, by the boundary conditions given in Equation (12), we can gain F (0) = f (0) - g (0) + h (0) = 1 and F (1) = f (1) - g (1) + h (1) = -1. As f (s) and g (s) are both continuous functions and the Intermediate Value Theorem in mathematics, we know there must exist a point at which $F (s) = 0,$ (17) holds for some s ∈ 0, 1. This just implies that the first adiabatic algorithm has infinite time complexity for any interpolating functions f, g and h if the overlap a equals zero.

Secondly, we consider the driving item $H_{e} = | φ_{0} 〉〈 φ_{0}^{⊥} |$ , and by using Equation (11), the time-dependent Hamiltonian of the adiabatic system will be rewritten as:

$\begin{matrix} \hat{H (s)} & = & f (I - | φ_{0} 〉〈 φ_{0} |) + g (I - | φ_{1} 〉〈 φ_{1} |) \\ + h (| φ_{0} 〉〈 φ_{0}^{⊥} |), for 0 \leq s \leq 1 . \end{matrix}$ (18)

With Equations (5–7), the Hamiltonian matrix of Equation (17) will be set as: $\hat{H (s)} = (\begin{matrix} b^{2} g h - abg \\ - abg f + a^{2} g \end{matrix}),$ (19) and we can easily work out the minimal gap of the system as:

$\begin{matrix} \underset{0 \leq s \leq 1}{g_{min}} & = & | E_{0} (s) - E_{1} (s) | \\ = & \sqrt{{(f - g)}^{2} + 4 a^{2} g (fa + bh)}, \end{matrix}$ (20)

When the overlap between φ₀〉 and φ₁〉 equals zero, the minimal gap is ${\underset{0 \leq s \leq 1}{g_{min}} |}_{a = 0} = | f - g |,$ (21)

With the boundary conditions given in Equation (12) and the Intermediate Value Theorem in mathematics, we know there must always exist a point to lead g_min to equal zero. This just implies that the second adiabatic algorithm may fail for any interpolating functions f, g and h if the overlap a equals zero.

Thirdly, we consider another driving item H_e = |φ₀ 〉〈 φ₀| + |φ₁ 〉〈 φ₁|, and by using Equation (11), the time-dependent Hamiltonian of the adiabatic system will be rewritten as:

$\begin{matrix} \hat{H (s)} & = & f (I - | φ_{0} 〉〈 φ_{0} |) + g (I - | φ_{1} 〉〈 φ_{1} |) \\ + h (| φ_{0} 〉〈 φ_{0} | + | φ_{1} 〉〈 φ_{1} |), for 0 \leq s \leq 1 . \end{matrix}$ (22)

With Equations (5–7), the Hamiltonian matrix of Equation (22) will be set as: $\hat{H (s)} = (\begin{matrix} h + b^{2} g - abg \\ - abg h + f + a^{2} g \end{matrix}),$ (23) and we can easily work out the minimal gap of the system as: $\underset{0 \leq s \leq 1}{g_{min}} = | E_{0} (s) - E_{1} (s) | = \sqrt{{(f + g)}^{2} + 4 {gfb}^{2})},$ (24)

When the overlap a between φ₀〉 and φ₁〉 equals zero, the minimal gap is ${\underset{0 \leq s \leq 1}{g_{min}} |}_{a = 0} = | f - g |,$ (25)

With the boundary conditions given in Equation (12) and the Intermediate Value Theorem in mathematics, we know there must always exist a point to lead g_min to equal zero. This implies that the third adiabatic algorithm may fail for any interpolating functions f, g and h if the overlap a equals zero.

Fourthly, we consider the fifth kind of driving item H_e as $| φ_{0} 〉〈 φ_{0}^{⊥} | + | φ_{0}^{⊥} 〉〈 φ_{0} |$ , and by using Equation (11), the time-dependent Hamiltonian $\hat{H (s)}$ of the adiabatic system will be rewritten as:

$\begin{matrix} \hat{H (s)} & = & f (I - | φ_{0} 〉〈 φ_{0} |) + g (I - | φ_{1} 〉〈 φ_{1} |) \\ + h (| φ_{0} 〉〈 φ_{0}^{⊥} | + | φ_{0}^{⊥} 〉〈 φ_{0} |), \\ for 0 \leq s \leq 1 . \end{matrix}$ (26)

With Equations (5–7), the Hamiltonian matrix of Equation (37) will be set as: $\hat{H (s)} = (\begin{matrix} b^{2} g h - abg \\ h - abg f + a^{2} g \end{matrix}) .$ (27)

The minimal gap of the system can be inferred as:

$\begin{matrix} \underset{0 \leq s \leq 1}{g_{min}} & = & | E_{0} (s) - E_{1} (s) | \\ = & \sqrt{{(f + (b^{2} - a^{2}) g)}^{2} + 4 {(h - abg)}^{2}} . \end{matrix}$ (28)

It is obvious that the adiabatic algorithm can evolve successfully when the overlap a = 0. However, when the conditions f = (a² - b²) g and h = abg is satisfied, the evolution will fail. We can construct a new function as F (s) = f (s) + (b² - a²) g (s). With the boundary conditions given in Equation (12), then we can get F (0) = f (0) - g (0) = 1 and F (1) = f (1) - g (1) + h (1) = b² - a². If the a² > 1/2, by the fact that f (s) and g (s) are both continuous functions and Intermediate Value Theorem in mathematics, we known there must exist a point for which $F (s) = 0,$ (29) holds for some s ∈ 0, 1. Therefore, the performance of this algorithm as Equation (26) is related to the overlap of the initial and final state.

Finally, we consider the driving item H_e as |φ₀ 〉〈 φ₁| + |φ₁ 〉〈 φ₀|, and by using Equation (11), the time-dependent Hamiltonian $\hat{H (s)}$ of the adiabatic system will be rewritten as:

$\begin{matrix} \hat{H (s)} & = & f (I - | φ_{0} 〉〈 φ_{0} |) + g (I - | φ_{1} 〉〈 φ_{1} |) \\ + h (| φ_{0} 〉〈 φ_{1} | + | φ_{1} 〉〈 φ_{0} |), \\ for 0 \leq s \leq 1 . \end{matrix}$ (30)

With Equations (5–7), the Hamiltonian matrix of Equation (27)will be set as: $\hat{H (s)} = (\begin{matrix} b^{2} g + 2 ah bh - abg \\ bh - abg f + a^{2} g \end{matrix}) .$ (31)

The eigenvalues of it are readily available: $E_{0} = \frac{A + B}{2}, E_{1} = \frac{A - B}{2},$ (32) in which $A = - (g + f + 2 ah),$ (33) $B = \sqrt{{(f + g)}^{2} + 4 h^{2} - 4 ah (f + g) - 4 b^{2} gf} .$ (34)

The minimum gap of the system can be inferred as:

$\begin{matrix} \underset{0 \leq s \leq 1}{g_{min}} & = & | E_{0} (s) - E_{1} (s) | \\ = & \sqrt{{(f + g - 2 ah)}^{2} + 4 b^{2} (h^{2} - gf)} . \end{matrix}$ (35)

When the overlap a between φ₀〉 and φ₁〉 equals zero, the minimal gap is ${\underset{0 \leq s \leq 1}{g_{min}} |}_{a = 0} = \sqrt{{(f - g)}^{2} + 4 h^{2}},$ (36)

This time, when the overlap a between the initial and final states equals zero, the adiabatic evolution will not fail. It means that this extra item is efficient in circumstances that the initial state has a zero overlap with the final state.

Actually, other researchers [19, 20] also have shown that AQC is equivalent to standard quantum computing. We can clearly see this problem in a 2- dimension by using Grover-quantum as paper [7] stated.

We achieve this target by first discretizing the running time T and then applying the Trotter formula at each discrete time. Every interval will cause the initial state get into a new state |φ′ 〉〈 φ′|, and the mediate state will get a new rotation angel θ with the final state |φ 〉〈 φ|. It is obviously see that θ > 0. As we known that, if the rotation θ is not equals zero in every interval time, the system will find the final state at last.

The first three kinds of extra item will make the rotation angel equals zero when the overlap of the initial and final state has a zero overlap. The fourth kind of extra item will always make the rotation angel equals zero when the overlap of the system greater than $\frac{\sqrt{2}}{2}$ . Therefore, all four kinds of extra Hamiltonian has their refrains to keep the adiabatic computation complete.

It seems the fifth kind of adiabatic quantum algorithm will overcome the difficulty to keep the adiabatic evolution complete. However, if we use f = 1 – s, g = s, h = s(1– s) to substitute Equation (30), the system Hamiltonian matrix will be: $\hat{H (s)} = (\begin{matrix} {sb}^{2} + 2 as (1 - s) sb (1 - s - a) \\ sb (1 - s - a) 1 - {sb}^{2} \end{matrix}),$ (37) then we can simply figure out the minimal gap of the system: $\underset{0 \leq s \leq 1}{g_{min}} = | E_{0} (s) - E_{1} (s) | = | a - 1 / 2 | .$ (38)

The time complexity of the system can be found obviously as: $T \in O ({| a - 1 / 2 |}^{- 2}) .$ (39)

The adiabatic algorithm with the driving item |φ₀ 〉〈 φ₁| + |φ₁ 〉〈 φ₀| also has a poor performance when the fidelity of the system equals $\frac{1}{2}$ , and we can apparently find that its evolving time is infinite.

In order to further understand the reason that lead to a constant running time for adiabatic quantum computation, we analyze the two specific adiabatic models [12, 13] as mentioned above, and find that both two models have increased the value of the relevant back-diagonal elements of time-dependent Hamiltonian, which causes the minimal gap increasing to a nonzero constant, so that the time complexity of these models can achieve O (1). The result reveals the fact that the relevant back-diagonal elements of time-dependent Hamiltonian is the key factor to affect the time complexity of adiabatic computation, which is just the same as what the Ref. [15] stated, the entanglement of initial state and final state has affected the time complexity of adiabatic computation.

Then we add σ to matrix element B, and the Hamiltonian matrix will be transformed as: $\tilde{H (s)} = (\begin{matrix} A & B + σ \\ B + σ & C \end{matrix}) .$ (40)

The value of the minimal gap is easily obtained as: $g_{min} = \sqrt{{(A - C)}^{2} + 4 {(B + σ)}^{2}} .$ (41)

Now, A - C and B + σ belong to O (1), the minimal gap must belong to O (1).

More specially, we consider the following Hamiltonian as: $\tilde{H (s)} = f (s) H_{i} + g (s) H_{f} + h (s) \tilde{H_{e}},$ (42) where the range of functions f (s), g (s) & h (s) is a constant, and $\tilde{H_{e}} = | φ_{0} 〉〈 φ_{0} ⊥ | + | φ_{0} ⊥ 〉〈 φ_{0} |,$ (43) in which |φ₀⊥ 〉 is the orthogonal state to the initial state |φ₀〉 in the two-dimensional Hibernate space with |φ₀〉, |φ₁ 〉 basic. By using Equations (8–10), the Hamiltonian can be recast as: $\tilde{H (s)} = (\begin{matrix} b^{2} g (s) & h (s) + (- abg) \\ h (s) + (- abg) & f (s) + a^{2} g (s) \end{matrix}) .$ (44)

The value of the minimal gap is easily obtained as: $\tilde{g_{min}} = \sqrt{h {(s)}^{2} + a^{2} g (s) f (s) - abh (s) g (s)} .$ (45)

In order to keep the balance of Hamiltonian matrix, we should consider all elements by using this method. The following Hamiltonian can be considered as: $H (s) = \bar{f (s)} H_{i} + \bar{g (s)} H_{f},$ (46) where $\bar{f (s)} = \frac{1 - s}{a}$ , and $\bar{g (s)} = \frac{s}{a}$ . By using Equation (8–10), the Hamiltonian as can be recast as: $H (s) = (\begin{matrix} \frac{b^{2} g (s)}{a} & \frac{1}{a} \cdot (- abg (s)) \\ \frac{1}{a} \cdot (- abg (s)) & \frac{f (s) + a^{2} g (s)}{a} \end{matrix}) .$ (47)

We can easily get the minimal gap with Equations (21 and 22): $g_{min} = {\sqrt{4 f (s) g (s)}}_{| min, 0 \leq s \leq 1} \in O (1) .$ (48)

It is easy to see that the model as Equation (19) is a realization of this kind of mechanism, which multiples a factor as 1/ - a to the original Hamiltonian.

In this section, we have analysed all possible forms of the extra Hamiltonian in adiabatic computation and the result is shown in Table 1. No matter what the interpolating function setting is, the first three kinds of extra Hamiltonian can not complete the adiabatic evolution when the overlap between the initial and final states equals zero. The fourth kind of extra Hamiltonian is efficient for the adiabatic evolution where the initial state has a zero overlap with the final state. But if the overlap a² > 1/2, No matter what the interpolating function setting is, the fourth kind of adiabatic algorithm will always exist a breakpoint to make the adiabatic fail. In other words, the last form of the extra Hamiltonian is beneficial for the adiabatic evolution. However, we also find that the fifth kind of adiabatic algorithm owns a breaking point in its evolution path if the interpolating functions are set as f = 1 – s, g = s, h = s(1 – s). To compare with the former fourth kinds of adiabatic algorithm, we set a specific form of the interpolating functions in the last adiabatic algorithm. Only with a specific interpolating functions, the last one can fail in its adiabatic evolution. Does there exist an adiabatic model which can always provide an efficient evolution when the system owns an arbitrary overlap? If we give other special interpolating functions, the adiabatic algorithm with this extra Hamiltonian |φ₀ 〉〈 φ₁| + |φ₁ 〉〈 φ₀| will show different efficiency in adiabatic evolution. We will discuss the details in the next section. This is also our motivation to discuss the forms of extra items for removing this common fault of these algorithms.

Table 1

Summary of the performance of the five kinds of extra items in the nonlinear adiabatic algorithm as $\hat{H (s)} = {fH}_{0} + {gH}_{1} + {hH}_{e}$

Different forms of the extra items	Value of the overlap a	Interpolating Functions	Performance
H_e = \|φ₀ 〉〈 φ₀\|	a = 0	f(0) = g(1) = 1 h(0) = h(1) = 0	Failure
$H_{e} = \| φ_{0} 〉〈 φ_{0}^{⊥} \|$	a = 0	f(0) = g(1) = 1 h(0) = h(1) = 0	Failure
H_e = \|φ₀ 〉〈 φ₀\| + H_e = \|φ₁ 〉〈 φ₁\|	a = 0	f(0) = g(1) = 1 h(0) = h(1) = 0	Failure
$H_{e} = \| φ_{0} 〉〈 φ_{0}^{⊥} \| + H_{e} = \| φ_{0}^{⊥} 〉〈 φ_{0} \|$	a² > 1/2	f(0) = g(1) = 1 h(0) = h(1) = 0	Failure
H_e = \|φ₀ 〉〈 φ₁\| + H_e = \|φ₁ 〉〈 φ₀\|	a = 1/2	f = 1-s,g = s, h = s(1-s)	Failure

3 Strengthening conditions of the interpolating functions for the fourth adiabatic algorithm

According to the second section, it is acknowledged that three kinds of adiabatic models will lose their efficacy when the overlap of the system equals a specific value. How to adjust interpolating functions to make the last adiabatic algorithm provide an efficient evolution no matter what overlap the system owns? The details will be discussed in this section.

We present that the structure of local Hamiltonian is the essentially cause leading a success or a failure in adiabatic evolution. The local Hamiltonian must have a structure including a flipping matrix of evolution, which is the key factor to make initial state flip to the orthogonal state. In terms of a general quantum adiabatic models without driving Hamiltonian, when its initial state and final state is orthogonal, it will lose its flipping matrix as σ (x) Pauli matrix we discussed above, so it fails at last. In terms of a nonlinear quantum adiabatic model with a driving Hamiltonian, the structure of local Hamiltonian always contains the flipping matrix like σ (x) Pauli matrix, so it can keep an effcient evolving to find the final state at last.

It has now become evident to us that the time complexity of the nonlinear model has a close relationship with the overlap a in Equation (35). In order to ensure the efficiency of the nonlinear model, we must avoid the minimal gap as Equation (35) equals zero. This problem will be discussed in three cases.

In the case of a = 1, we ignore this meaningless situation because the initial state will be the same as the final state.

In the case of a = 0, by using Equation (35), the minimal gap of the system can be rewritten as: $\underset{0 \leq s \leq 1}{g_{min}} = | E_{0} (s) - E_{1} (s) | = \sqrt{{(f - g)}^{2} + 4 h^{2}} .$ (49)

To make sure there does not exist any s ∈ [0, 1] leading the minimal gap to zero, we must have the following condition: $h \neq 0, when g = f .$ (50)

In the case of 0 < a < 1, with Equation (35), it can be naturally obtained that if $h^{2} > gf$ (51) is satisfied, the minimal gap will not equal zero. It is inferred that Equation (41) also satisfies Equation (42). What if the condition (h² = gf) is satisfied? Suppose the minimal gap equal zero and (h² = gf) is satisfied and by applying Equation (35), we can easily get $(f + g - 2 ah) = 0$ (52) and $(h^{2} - gf) = 0 .$ (53)

From Equation (35), we can get

$\begin{matrix} h^{2} - gf \\ = \frac{1}{4 a^{2}} \cdot {{[f + (1 - 2 a^{2}) g]}^{2} + 4 g^{2} {(ab)}^{2}} \\ = 0 . \end{matrix}$ (54)

We can easily obtain $f (ɛ) = g (ɛ) = h (ɛ) = 0, \exists ɛ \in (0, 1),$ (55) which does not satisfy our condition Equation (39). Therefore, it can identified that if Equation (42) is true and Equation (41) is satisfied, the minimal gap will never equal zero, and the model is still efficient.

What if the condition (h² < gf) is satisfied? According to Equation (35), we can get

$\begin{matrix} \underset{0 \leq s \leq 1}{g_{min}} & = & {(f + g - 2 ah)}^{2} - 4 b^{2} gf + 4 b^{2} h^{2} \\ = & {(f + g)}^{2} + 4 h^{2} - 4 ah (f + g) - 4 b^{2} gf \\ \geq & 4 fg + 4 h^{2} - 8 ah \sqrt{fg} - 4 b^{2} gf \\ = & 4 {(a \sqrt{fg} - h)}^{2} \end{matrix}$ (56)

By using Equation (47), we can easily find that if $a \sqrt{fg} - h$ equals zero, the adiabatic algorithm will fail. When $a \sqrt{fg} - h = 0$ , and 0 < a < 1, we can induce that h² ≤ fg. Therefore, if the condition (h² < gf) is satisfied, the adiabatic algorithm may not evolve successfully all the time. Stated thus, we have discussed the relationship between the interpolating functions and the adiabatic algorithm. Consequently, we can draw a conclusion that the strengthening conditions of the adiabatic algorithm are $h^{2} (s) \geq g (s) f (s), \forall s \in (0, 1)$ (57) and $h (s) \neq 0, when (g (s) = f (s)), \forall s \in [0, 1] .$ (58)

By using Equation (35), we can easily figure out the time complexity of this adiabatic algorithm. The minimal gap can be rewritten as:

$\begin{matrix} \underset{0 \leq s \leq 1}{g_{min}} \\ = {\sqrt{{(f - g)}^{2} + 4 h^{2} - 4 ah (f + g) + 4 a^{2} fg)^{2}}}_{| 0 \leq s \leq 1} . \end{matrix}$ (59)

While the interpolating functions f reach at f = g, Equation (50) can be rewritten as:

$\begin{matrix} \underset{0 \leq s \leq 1}{g_{min}} \\ = {\sqrt{4 h^{2} - 8 ahg + 4 a^{2} g)^{2}}}_{| 0 \leq s \leq 1} = 2 | h - ag | . \end{matrix}$ (60)

According to, we can easily get the adiabatic algorithm has constant time complexity with the adiabatic theorem based on literature. By running a simple analysis, however, we note that at this time the implementation of the driving Hamiltonian takes another complexity compared with the usual adiabatic evolution such as linear adiabatic quantum search algorithm. That is to say, we have shifted the original time complexity of the algorithm to the complexity of implementing the driving Hamiltonian added, and this is consistent with our intuition. Another similar nonlinear path has been studied in literature for removing the failure of the linear adiabatic and local adiabatic algorithms for the evolution from an initial state to a state that is orthogonal or almost orthogonal to it.

With the help of these strengthening conditions, we can extend the model as Equation (30) easily. For instance, we change the interpolating function h = s (1 - s) into $h = \sqrt{(1 - s) s}$ , which satisfies Equations (48 and 49), and then the Hamiltonian H (s) can be rewritten as: $\hat{H (s)} = (1 - s) H_{1} + {sH}_{2} + \sqrt{s (1 - s)} H_{e},$ (61) the minimal gap of the system can be obtained as: $\underset{0 \leq s \leq 1}{g_{min}} = {\sqrt{{(1 - 2 a \sqrt{(1 - s)} s)}^{2}}}_{| 0 \leq s \leq 1} = | (1 - a) | .$ (62)

We ignore the case of a = 1, so the time complexity of this extensional one can be easily estimated with Equation (35): $T \in O ({(1 - a)}^{- 2}) \in O (1)$ (63)

We can find the extensional nonlinear model will have constant time complexity, and it can always evolve successfully where the overlap of system can be an arbitrary value.

We also can change the interpolating functions $h = sin (\frac{π s}{2}) • cos (\frac{π s}{2})$ , which is not satisfies Equations (48 and 49), and then the Hamiltonian H (s) can be rewritten as:

$\begin{matrix} \hat{H (s)} & = & (1 - s) H_{1} + {sH}_{2} \\ + sin (\frac{π s}{2}) • cos (\frac{π s}{2}) H_{e} \end{matrix}$ (64) the minimal gap of the system can be obtained as:

$\underset{0 \leq s \leq 1}{g_{\min}} = \sqrt{{(1 - 2 s)}^{2} + | \sin (\frac{π s}{2}) • \cos (\frac{π s}{2}) -as} | |_{0 \leq s \leq 1}$ (65)

When the interpolating functions f = g is satisfied, the algorithm with this extra Hamiltonian whose structure as |φ₀ 〉〈 φ₁| + |φ₁ 〉〈 φ₀| will not always evolve successfully where the overlap of system equals $\frac{1}{2}$ .

This strengthening conditions is the key factor to keep the adiabatic algorithm evolve successfully whose extra Hamiltonian structure as |φ₀ 〉〈 φ₁| + |φ₁ 〉〈 φ₀|. It seems the strengthening conditions is also generic for an arbitrary quantum adiabatic model whose Hamiltonians can be transformed into the form as: $H (s) = f^{'} (s) H_{1}^{'} + g^{'} (s) H_{2}^{'} + h^{'} (s) H_{e}^{'},$ (66) where $H_{e}^{'} = H_{1}^{'} H_{2}^{'} + H_{2}^{'} H_{1}^{'} .$ (67)

According to ref, the existence of entanglements of initial state and final state is the basic condition for an adiabatic evolution, which indicates this form of local Hamiltonians as Equation (57) is necessary to keep an effcient evolution in quantum computation. By using these strengthening conditions, we can determine the adiabatic quantum algorithm whether there exists a point on the evolution path to make it fail. With Equations (5–7), the Hamiltonian H(s) of a general adiabatic model can be transformed into the form as:

$\begin{matrix} H (s) = (1 - {sb}^{2}) (I - | α 〉〈 α |) + {sb}^{2} (I - | β 〉〈 β |) \\ - sab (| α 〉〈 β | + | β 〉〈 α |) = f^{'} H_{1}^{'} + g^{'} H_{2}^{'} + h^{'} H_{e}^{'} \end{matrix}$ (68) in which

$\begin{matrix} H_{1}^{'} & = & I - | α 〉〈 α |, H_{2}^{'} = I - | β 〉〈 β |, \\ H_{e}^{'} & = & | α 〉〈 β | + | β 〉〈 α |, \end{matrix}$ (69) and $f^{'} = 1 - {sb}^{2}, g^{'} = {sb}^{2}, h^{'} = - sab .$ (70)

We can easily get the result h^′2 - f′g′ < 0, which is not satisfied with the conditions as Equation (48), so it must set a break point to disable the adiabatic evolution. This approach yields the same conclusion reached in, where the intermediate value theorem showed there must exist a point to where f - g = 0.

In this section, we conclude the conditions of interpolating functions in the adiabatic algorithm with extra Hamiltonian in the form of |φ₀ 〉〈 φ₁| + |φ₁ 〉〈 φ₀|. By compute the minimal gap of the adiabatic system, we find that there must exist the two conditions of the interpolating functions to make the minimal gap not be zero which is based the adiabatic theorem. Moreover, with the aid of these conditions, we can extend the adiabatic algorithm to avoid the adiabatic-failure problem efficiently, in spite of what fidelity the system owns. And we also give another forms of interpolating function, which is not satisfied with the condition. At last, we find that the system will fail when the interpolating functions $s = \frac{1}{2}$ . More important, we compute the running time complexity of the adiabatic algorithm with the special extra Hamiltonian. And the new algorithm has better evolution time complexity, which can make the evolution complete at a constant time than the general adiabatic algorithm which forms as H (s) = fH₁ + gH₂. Although, the time complexity may be shifted to the complexity of implementing the driving Hamiltonian added. Finally, we use this strengthening conditions to judge the efficiency of the general adiabatic algorithm. And we find that it can be generic conditions to determine the adiabatic quantum algorithm whether there exists a point on the evolution path to make it fail.

4 Conclusion

In summary, we present five kinds of the possible forms of extra Hamiltonian in adiabatic computation. The former three kinds of extra Hamiltonians will lose their efficiency when the overlap of the initial and final state equals zero. And the fourth kind of the extra Hamiltonian will make the adiabatic computation powerless when the overlap between the initial and final state greater than $\frac{\sqrt{2}}{2}$ . Only the structure as |φ₀ 〉〈 φ₁| + |φ₁ 〉〈 φ₀| of the extra Hamiltonian is beneficial to the adiabatic computation. Then in order to make the adiabatic algorithm more efficient for an arbitrary overlap, we further compute the strengthening conditions on interpolating functions for the adiabatic model with extra Hamiltonian. With the aid of these conditions, we can have extended the nonlinear models to avoid the adiabatic-failure problem efficiently. In this paper, we give a simple example of the final kind of the extra Hamiltonian in the adiabatic algorithm, which provide good performance in the adiabatic evolution. But as what we have stated, the time complexity is shifted to the complexity of implementing the driving Hamiltonian added. Moreover, we can also determine whether a quantum adiabatic model has a break point causing the adiabatic evolution to fail by these conditions. These conditions may help us to design more efficient adiabatic algorithms.

Footnotes

Acknowledgments

We gratefully acknowledge the support of the National Natural Science Foundation of China under Grant Nos. 61173050 and 61402188.

References

Song

X.K.

, Zhang

, Ai

, et al., Shortcuts to adiabatic holonomic quantum computation in decoherence-free subspace with transitionless quantum driving algorithm[J], 18(2) (2016), 569–577.

Hen

and Young

A.P.

, Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems[J], Physical Review E Statistical Nonlinear & Soft Matter Physics84(1) (2011), 061152.

Altshuler Bertr

and Halperin

, Anderson localization makes adiabatic quantum optimization fail[J], Proceedings of the National Academy of Sciences of the United States of America107(28) (2010), 12446.

Garnerone

, Zanardi

and Lidar

D.A.

, Adiabatic quantum algorithm for search engine ranking[J], Physical Review Letters108(23) (2012), 230506.

Bian

, Chudak

, Macready

W.G.

, et al., Experimental determination of Ramsey numbers [J], Physical Review Letters111(13) (2013), 130505.

Somma

R.D.

, Nagaj

and Kieferová

, Quantum speedup by quantum annealing[J], Physical Review Letters109(5) (2012), 050501.

Aharonov

, Van Dam

, Kempe

, et al., Adiabatic quantum computation is equivalent to standard quantum computation[J], Siam Review50(4) (2004), 755–787.

Quiroz

and Lidar

D.A.

, High fidelity adiabatic quantum computation via dynamical decoupling[J], Physical Review A86(4) (2012), 2476–2482.

Nagaj

and Mozes

, New construction for a QMA complete three-local Hamiltonian[J], Journal of Mathematical Physics48(7) (2007), 258–264.

10.

Nagaj

, Fast universal quantum computation with railroad-switch local Hamiltonians[J], Journal of Mathematical Physics51(6) (2009), 11–383.

11.

Farhi

, Goldstone

, Gutmann

, et al., How to make the quantum adiabatic algorithm fail[J], International Journal of Quantum Information6(03) (2011), 503–516.

12.

Farhi

, Goldston

, Gosset

, et al., Quantum adiabatic algorithms, small gaps, and different paths[J], Quantum Information & Computation11(3) (2010), 181–214.

13.

Peschina

, Classical and quantum statistical analysis of a constraint satisfaction problem[J], Anesthesiology3(3) (2010), 185–208.

14.

Andrecut

and Ali

M.K.

, Unstructured adiabatic quantum search[J], International Journal of Theoretical Physics43(4) (2004), 925–931.

15.

Waseem

, Ahmed

, Irfan

, et al., Three-qubit Grover’s algorithm using superconducting quantum interference devices in cavity-QED[J], Quantum Information Processing12(12) (2013), 3649–3664.

16.

Altshuler Bertr

and Halperin

, Anderson localization makes adiabatic quantum optimization fail[J], Proceedings of the National Academy of Sciences of the United States of America107(28) (2010), 12446.

17.

Altshuler

, Krovi

and Roland

, Anderson localization casts clouds over adiabatic quantum optimization[J], Computer Science107(28) (2009), 12446–12450.

18.

Choi

, Different adiabatic quantum optimization algorithms for the NP-complete exact cover problem[J], Proceedings of the National Academy of Sciences of the United States of America108(7) (2011), 19–20.

19.

Somma

R.D.

, Nagaj

and Kieferová

, Quantum speedup by quantum annealing[J], Physical Review Letters109(5) (2012), 050501.

20.

Pudenz

K.L.

and Lidar

D.A.

, Quantum adiabatic machine learning[J], Quantum Information Processing12(5) (2011), 2027–2070.