Quantum speed limit is a fundamental concept in quantum mechanics, and it aims at finding the minimum time scale or the maximum dynamical speed for some fixed targets. For example, when unitary evolution of pure states is considered, an achievable QSL is given as τ ≥ dFS/ΔE, where dFS is the Fubini–Study distance between the initial and target states,[1] and ΔE is the time-averaged standard deviation of a given Hamiltonian, which plays the role of the average speed.[2] The first rigorous derivation of the quantum speed limit can be dated back to Mandelstam and Tamm.[3]
Since the advent of quantum theory, the time-energy uncertainty relation ΔEΔT ≥ ℏ/2 has been a controversial issue with regard to its appropriate formalization, validity, and possible meanings.[4] It cannot be derived from any commutator relation, which is due to the lack of a well-defined time operator in quantum mechanics. The authors of Ref. [5] showed that ΔE cannot be regarded as the minimum dispersion of an energy measurement of duration ΔT. Instead, ΔT corresponds to the minimum time span that quantum systems with constant energy and initial energy spread ΔE need to evolve from one state to another orthogonal state.[6–9] The relation τQSL ≃ ℏ/ΔE gives the quantum speed limit time of a system. In Refs. [10,11], the energy-time uncertainty relation for time-independent systems has been further extended, in which the quantum speed limit time for general mixed states, not necessarily orthogonal, is determined as a function of their geometrical angle which is given by the Bures length.[12]
Recently, Kieu obtained a new class of time-energy uncertainty relations directly derived from the Schrödinger equations for time-dependent Hamiltonians.[13] For particularly interesting cases there, the results for the time-independent Hamiltonians and also for the time-varying Hamiltonians which are employed in quantum adiabatic evolution[14,15] are presented explicitly. With Grover’s search as an example,[16] the estimate of the lower bound on computational time for it is shown, from which the role of required energy resources is particularly emphasized there, besides the space and time complexity, for the physical process of quantum computation. Inspired by this work, Okuyama and Ohzeki derived a speed limit for the imaginary-time Schrödinger equation, and they found that, using this new speed limit, the optimal computational time of the imaginary-time quantum annealing of Grover’s search is bounded from below by the logarithm of the size of the problem.[17] This result is consistent with a previous study in which both of analytical and numerical methods have been applied for the Grover problem in imaginary-time quantum annealing to reach the same conclusion.[18]
However, it is easy to see that, in the works of Refs. [13,17], an example seems to lack for an illustration purpose when the speed limit or the time-energy uncertainty relation is applied to the time-independent Hamiltonian case. Thus in the present paper, we make up this gap by showing that the continuous version of Grover’s search, or the analog analogue to Grover’s algorithm called by Farhi et al.,[19] is just such a good toy example for the goal. It will be found that, for the time-energy uncertainty relation applied to the quantum evolution of Grover’s problem in the continuous setting, the resulting time complexity matches the well known square root bound,[20] whereas the optimal time is logarithm in the problem size for the speed limit applied to the same kind of problem. Thus from the results here, we once again see that the optimal schedules for the quantum annealing by the imaginary-time and real-time Schrödinger equations differ greatly.
Now, let us firstly turn to the case that the time-energy uncertainty relation in Ref. [13] is applied to the time-independent Hamiltonian. For this case, we consider the following Schrödinger equation with a time-independent Hamiltonian H:
$$ \begin{eqnarray}{\rm{i}}\hslash \displaystyle \frac{{\rm{d}}}{{\rm{d}}t}|\psi (t)\rangle =H|\psi (t)\rangle,\,|\psi (t)\rangle =|{\phi }_{0}\rangle,\end{eqnarray}$$ (1)
and also consider another state |ϕ(t)〉 which satisfies a closely related Schrödinger equation
$$ \begin{eqnarray}{\rm{i}}\hslash \displaystyle \frac{{\rm{d}}}{{\rm{d}}t}|\phi (t)\rangle =\beta {\bf{1}}|\phi (t)\rangle,\,|\phi (t)\rangle =|{\phi }_{0}\rangle,\end{eqnarray}$$ (2)
in which β is an arbitrary constant but not equal to zero so that it results in a phase ambiguity , and 1 denotes the identity matrix. It was found by Kieu that the following inequality holds for Eq. (1):
$$ \begin{eqnarray}\hslash \sqrt{2}\le \Delta {t}_{\perp }\times \Delta {E}_{0},\end{eqnarray}$$ (3)
where
$$ \begin{eqnarray}\Delta {E}_{0}=\sqrt{\langle {\phi }_{0}|{H}^{2}|{\phi }_{0}\rangle -{\langle {\phi }_{0}|H|{\phi }_{0}\rangle }^{2}}\end{eqnarray}$$ (4)
is the energy spread of the initial state, and Δt⊥ is the time at which the initial state evolves into a state orthogonal to it, 〈ψ(Δt⊥)|ϕ0〉 = 0. It can be noted that in inequality (3), Eq. (2) only serves as an ancillary equation, and β in it has been set as β = 〈ϕ0|H|ϕ0〉 in Ref. [13].For the analog to Grover’s algorithm, the system Hamiltonian is time-independent and given as[19]
$$ \begin{eqnarray}H=E|s\rangle \langle s|+E|w\rangle \langle w|,\end{eqnarray}$$ (5)
where |w〉 is the target state, |s〉 is the initial state which is usually chosen as the uniform superposition of all the elements in an unstructured database, , and E is some positive constant. From Eq. (5), it is easy to obtain
$$ \begin{eqnarray}\sqrt{\langle {\phi }_{0}|{H}^{2}|{\phi }_{0}\rangle -{\langle {\phi }_{0}|H|{\phi }_{0}\rangle }^{2}}=E\sqrt{\displaystyle \frac{1}{N}-\displaystyle \frac{1}{{N}^{2}}}\end{eqnarray}$$ (6)
after some calculations and noting that . Therefore, from inequality (3), we can reach
$$ \begin{eqnarray}\Delta {t}_{\perp }\ge \displaystyle \frac{\hslash \sqrt{2}}{E\sqrt{1/N-1/{N}^{2}}}.\end{eqnarray}$$ (7)
For N ≫ 1, we can further reduce the above inequality to the following one,
$$ \begin{eqnarray}\Delta {t}_{\perp }\ge \displaystyle \frac{\hslash \sqrt{2}}{E}\times \sqrt{N}\simeq O(\sqrt{N}).\end{eqnarray}$$ (8)
Thus, we can see that, by the time-energy uncertainty relation given in Ref. [13], the analog analogue of Grover’s problem solved by quantum evolution driven by the real-time Schrödinger equation also has a square root speedup compared with classic computer search. This is consistent with the result of Farhi et al. given in Ref. [19], whereas the time complexity there was obtained by the analogue method used in the analysis of the quantum circuit model of Grover’s algorithm.Now, let us argue why the time-energy uncertainty relation leads to a square root speedup in real time evolution. In Hermitian quantum mechanics, the most general 2 × 2 Hermitian has the form
$$ \begin{eqnarray}H=\left(\begin{array}{cc}s\, & r{{\rm{e}}}^{-{\rm{i}}\theta }\\ r{{\rm{e}}}^{{\rm{i}}\theta }\, & u\end{array}\right),\end{eqnarray}$$ (9)
where the four parameters r, s, u, and θ are real. The eigenvalue constraint E+ – E– = ω of this matrix reads
$$ \begin{eqnarray}{\omega }^{2}={(s-u)}^{2}+4{r}^{2}.\end{eqnarray}$$ (10)
From Ref. [21], we know that the optimal time for the quantum evolution from an initial state
$$ \begin{eqnarray}|{\phi }_{0}\rangle =\left(\begin{array}{c}1\\ 0\end{array}\right)\end{eqnarray}$$ (11)
to the final state
$$ \begin{eqnarray}|{\phi }_{1}\rangle =\left(\begin{array}{c}a\\ b\end{array}\right),\,(|a{|}^{2}+|b{|}^{2}=1)\end{eqnarray}$$ (12)
with this Hamiltonian can be given as
$$ \begin{eqnarray}\Delta t=\displaystyle \frac{2\hslash }{\omega }\arcsin |b|.\end{eqnarray}$$ (13)
We can see that express (13) resembles the time-energy uncertainty principle, and it is the statement that rate × × = distance. The constraint (10) on H is equivalent to placing a bound on the standard deviation ΔH of the Hamiltonian, where ΔH in a normalized state |ϕ〉 is given by . The maximum value of ΔH is ω/2. The speed of evolution of a quantum state is given by ΔH.[22] The distance between the initial state and the final state is δ = 2arccos|〉ϕ0|ϕ1〉|, which thus is fixed. The shortest time to achieve the evolution from |ϕ0〉 to |ϕ1〉 = e−i HΔt/ℏ|ϕ0〉 is bounded below. Since ΔH of the Hamiltonian in Eq. (9) is r, to minimize the time of quantum evolution, we can choose r = ω/2, which implies s = u. Returning to the setting of the analog analogue to the Grover problem, the Hamiltonian reads in the two-dimensional space
$$ \begin{eqnarray}H=E\left(\begin{array}{cc}1+{x}^{2}\, & x\sqrt{1-{x}^{2}}\\ x\sqrt{1-{x}^{2}}\, & 1-{x}^{2}\end{array}\right),\end{eqnarray}$$ (14)
in which . For N ≫ 1, we can think that the diagonal elements of this matrix are approximately equal to each other, and the off-diagonal elements are approximately equal to Ex. Thus, the minimum time of the quantum evolution from the initial state to the target state is , in which for N ≫ 1.It is noted that from Ref. [13], in fact, we have another inequality, i.e.,
$$ \begin{eqnarray}2\hslash \le \Delta {t}_{\forall }\times \sqrt{\Delta {E}_{0}^{2}+{E}_{0}^{2}},\,({E}_{0}=\langle {\phi }_{0}|H|{\phi }_{0}\rangle),\end{eqnarray}$$ (15)
which together with inequality (3) constitutes the energy-time uncertainty relation for time-independent quantum unitary processes. Then we can unify them into the generic form
$$ \begin{eqnarray}\Delta t=\max \left\{\displaystyle \frac{2\hslash }{\sqrt{\Delta {E}_{0}^{2}+{E}_{0}^{2}}},\displaystyle \frac{\sqrt{2}\hslash }{\Delta {E}_{0}}\right\},\end{eqnarray}$$ (16)
which is just like the classic Margolus–Levitin’s and Mandelstam–Tamm’s uncertainty relations shown in a unified way. In fact, unifying these uncertainty relations of Kieu is necessary. This can be seen from the following simple example. Suppose that the target state |w〉 is orthogonal to the the initial state |s〉. It is easy to verify that the inequality (3) cannot give a meaningful time complexity estimate for this special problem. However, from the early results like that in Ref. [23], we know that the true time complexity for the problem solved by quantum adiabatic evolution is O(1). Using Eq. (15), we can also obtain the same result rather directly. Also, it can seen from Eq. (16) that the quantum speed limit time is inversely proportional to the energy of the system (energy spread or energy expectation value of the initial state), so it is determined by the initial energy in the time-independent case. This should not be surprising as energy is the generator of quantum time evolution. Therefore, it can be physically understood that the quantum speed limit time strongly depends on the initial energy of the quantum system: the more the energy that has been pumped into a system and the more the states the energy distributed in, the faster the system will evolve. In the analog analogue of the Grover search problem, the parameter E in the driving Hamiltonian H is in O(1), so the quantum evolution time is given by . It is easy to see that when E is set as, for example, , the resulting time complexity of the quantum evolution is constant. This phenomenon is not new, and in fact has already been noticed in the early work of Ref. [24]. Even further, it can be expected that, if E has the form of an exponential factor in N, the quantum evolution time can thus be reduced exponentially. In physics, Ref. [25] gave an example for this, i.e., when the quantum evolution time is controlled by the mean energy and the latter is increased exponentially in time, as in the creation of a squeezed state in a modulated harmonic trap, the quantum speed limit time is exponentially reduced. On the other hand, it can be noted that the quantum speed limit time may also be increased when the energy of the system is decreased. In realistic scenario, Ref. [26] provided an example for it.Next, we turn to the imaginary-time quantum annealing of this continuous version of Grover’s problem. We firstly recall the speed limit for the time-independent systems. For this, we consider the following two imaginary-time Schrödinger equations
$$ \begin{eqnarray}\begin{array}{lll} & & -\displaystyle \frac{{\rm{d}}}{{\rm{d}}t}|\psi (t)\rangle =H|\psi (t)\rangle,\,-\displaystyle \frac{{\rm{d}}}{{\rm{d}}t}|\phi (t)\rangle =\beta {\bf{1}}|\phi (t)\rangle,\\ & & |\psi (0)\rangle =|\phi (0)\rangle =|{\psi }_{0}\rangle,\end{array}\end{eqnarray}$$ (17)
in which H is required to be a real positive-semidefinite matrix, |ψ(t)〉 and |ϕ(t)〉 are real vectors. For Eq. (17), the speed limit derived in Ref. [17] is given as follows:
$$ \begin{eqnarray}\begin{array}{lll} & & |||\psi (\tau)\rangle -\exp (-\tau \langle {\psi }_{0}|H|{\psi }_{0}\rangle)|\psi (0)\rangle ||\\ & \le & \sqrt{\langle {\psi }_{0}|{H}^{2}|{\psi }_{0}\rangle -{\langle {\psi }_{0}|H|{\psi }_{0}\rangle }^{2}}\displaystyle \frac{1-\exp (-\tau \langle {\psi }_{0}|H|{\psi }_{0}\rangle)}{\langle {\psi }_{0}|H|{\psi }_{0}\rangle }.\,\end{array}\end{eqnarray}$$ (18)
Now we use Eq. (18) to analyze the quantum annealing of the continuous version of Grover’s problem driven by the first equation in (17). Note that for the time-independent Hamiltonian given in Eq. (5), it can be verified that H is indeed real positive-semidefinite, which is needed in the imaginary-time quantum annealing. In the imaginary-time Schrödinger equation, the norm of the state is not preserved, so the case that the state |ψ(t)〉 reaches the target state |||ψ(τ)〉|||w〉 at time τ is considered. Substituting this target state into the left-hand side of Eq. (18), we can reach
$$ \begin{eqnarray}\begin{array}{lll} & & ||\,|||\psi (\tau)\rangle ||\,|w\rangle -{{\rm{e}}}^{-\tau \langle {\psi }_{0}|H|{\psi }_{0}\rangle }|\psi (0)\rangle ||\\ & = & [|||\psi (\tau)\rangle |{|}^{2}+{{\rm{e}}}^{-2\tau \langle {\psi }_{0}|H|{\psi }_{0}\rangle }-\displaystyle \frac{2}{\sqrt{N}}|||\psi (\tau)\rangle ||{{\rm{e}}}^{-\tau \langle {\psi }_{0}|H|{\psi }_{0}\rangle }{]}^{1/2}\\ & = & {[(|||\psi (\tau)\rangle ||-\displaystyle \frac{1}{\sqrt{N}}{{\rm{e}}}^{-\tau \langle {\psi }_{0}|H|{\psi }_{0}\rangle })}^{2}\\ & & +\left(1-\displaystyle \frac{1}{N}\right){{\rm{e}}}^{-2\tau \langle {\psi }_{0}|H|{\psi }_{0}\rangle }{]}^{1/2}\\ & \ge & \sqrt{1-\displaystyle \frac{1}{N}}{{\rm{e}}}^{-\tau \langle {\psi }_{0}|H|{\psi }_{0}\rangle }.\end{array}\end{eqnarray}$$ (19)
From Eqs. (18) and (19), we can obtain
$$ \begin{eqnarray}1-{{\rm{e}}}^{-\tau E(1+1/N)}\ge {{\rm{e}}}^{-\tau E(1+1/N)}\sqrt{N}(1+1/N).\end{eqnarray}$$ (20)
Multiplying both sides of the above inequality by e−τ E(1 + 1/N) and then taking logarithm of the resulting inequality, for N ≫ 1, we are finally led to
$$ \begin{eqnarray}\tau \ge \displaystyle \frac{\displaystyle \frac{1}{2}\mathrm{ln}N}{E}\simeq O(\mathrm{ln}N).\end{eqnarray}$$ (21)
Then we can see that the imaginary-time quantum annealing of the analog analogue of Grover’s search also has exponential speedup compared with the case of quantum evolution of the same problem but by the real-time Schrödinger equation.At first sight, it seems that this O(ln N) time scale of the above imaginary-time evolution is counter-intuition, because imaginary-time evolution often suggests that there exists decoherences. Decoherences may have a negative effect on quantum evolution. For example, in Ref. [27], it was found that decoherences could decrease the energy gap between the ground state and the first excited state. As a result, the time scale of evolution should be longer than real-time evolution. However, in imaginary-time dynamics, the transition from excited states to the ground state strongly influences and can not be ignored, which is quite unlike that in real-time dynamics, for which it is possible to prove the optimality of order by the time-energy uncertainty relations in Ref. [13]. From Ref. [18], we know that the O(ln N) time complexity of the imaginary-time quantum annealing of Grover’s search is realized by a linear scheduling, which is very different from O(N) required for that by the real-time Schrödinger equation. This difference is caused by the exponential decay of excited states in imaginary-time quantum annealing. Even if the Landau–Zener transition occurs, the imaginary-time quantum annealing can obtain a high success probability due to the fact that the energy gap reopens after the Landau–Zener transition and the exponential decay of excited states plays an important role in Grover’s search problem. In real-time quantum annealing, with respect to the adiabatic condition, it is a necessary condition to avoid the Landau–Zener transition for achieving high success probability. In contrast, in imaginary-time quantum annealing, it is a sufficient rather than necessary condition. Therefore, it is more important to utilize the exponential decay of excited states than to avoid the Landau–Zener transition for imaginary-time quantum annealing. On the other hand, the fundamental speed limit (18) can be used for proving the optimality of order ln N. The imaginary time adiabatic theorem[28] does not give the optimal schedule,[18] which means that the adiabatic time evolution has nothing to do with the optimality in imaginary-time dynamics although the adiabatic time evolution is closely related to the optimality in real-time dynamics. Lastly, the imaginary-time annealing is in fact not physically realistic, so the result in Ref. [17] only gives us the implication that there is a fundamental limit even in such non-physical systems.
Quantum annealing has attracted much interest in recent years, for instance, in quantum machine learning[29,30] and quantum algorithms.[31–33] In the previous work of Ref. [13], a new class of time-energy uncertainty relations was directly derived from the Schrödinger equations for real-time quantum annealing. Grover’s search employed in quantum adiabatic computation was presented as an example to illustrate for its applications. The time-independent Hamiltonians, Grover’s search also yielded a class of time-energy uncertainty relations using nearly the same method in the same paper. However, no example is shown for the latter case there. Therefore, in this paper, we present the continuous version of Grover’s search as an example to explain it. Recently, Okuyama and Ohzeki obtained a similar speed limit as in Ref. [13] but for the imaginary-time Schrödinger equation. Also, the time-independent Hamiltonian case has been considered by them, whereas an example was missing, still the quantum adiabatic Grover’s problem was shown in the time-varying case for applying that speed limit. We find that the analogue of Grover’s search can also serve as an instance for this goal.
As shown by our result, the quantum evolutions of the continuous version of Grover’s problem by real-time and imaginary-time Schrödinger equations can demonstrate very different algorithmic performances. Plus the previous results shown separately in Refs. [13,17], it seems to imply that the optimal quadratic speedup and logarithmic time complexity of quantum annealing are respectively generic in the above two scenarios.
In this work, the derivation for the conclusion in the real time evolution is based on non-relativistic quantum mechanics. In the Hermitian quantum mechanics, the optimal time evolution problem implies that finding the transformation |ϕ0〉→ e−i Ht|ϕ0〉 can provide the shortest time t = Δt under a given set of constraints.[34] The Hamiltonian (5) given by Farhi et al. satisfies this requirement because it is well known that the square-root speedup is optimal. However, in PT-symmetric quantum mechanics, the speed limit of evolution changes significantly without violating the uncertainty principle,[21] for example, the optimal time for evolving from an initial state to the target state can be arbitrarily small.
Lastly, it is known that the theory of quantum gravity is aimed to fuse general relativity with quantum theory into a more fundamental framework. The space of quantum gravity provides both the dynamic (unfixed) causality of general relativity and the uncertainty of quantum mechanics. As pointed out by the referee, it seems that an related left question for us to consider in the future is how about the results in this paper if quantum gravity is introduced as in Ref. [35]. For this, we may reach a form like the generalized uncertainty principle which includes the gravitational interaction between particles and photons,[36,37], e.g.,
$$ \begin{eqnarray}\varDelta x\ge \displaystyle \frac{\hslash c}{2\Delta E}+\alpha \displaystyle \frac{G}{{c}^{4}}\Delta E,\end{eqnarray}$$ (22)
where α∼ O(1). However, in the present paper we decide not to discuss this issue.
