Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Journal of Quantum Information

On the time–energy uncertainty relation of Kieu applied to quantum evolutions of Grover’s search

Jie Sun, Songfeng Lu

Published Aug 1, 2020• 1 citation
Publisher

Abstract

Recently, Kieu derived a new class of time–energy uncertainty relations, which is not only formal but also suitable for evaluating the speed limit of quantum dynamics. However, when this time–energy uncertainty relation was applied to study the quantum adiabatic Grover’s search, some approximation had been done for reaching the right conclusion. That is, the final state being orthogonal to the initial state in this problem was assumed which may cause confusion, while the truth is that the overlap between these two states is indeed very small when the problem size is very big but not equal to zero exactly. In this paper, we modify the time–energy uncertainty relation of Kieu applied to two quantum evolutions of Grover’s problem, and find that the resulting computational complexities match well with the previous works on this topic but without the need of making the assumption like that in the work of Kieu.

DOI
10.1142/s0219749920500215

Related papers

On the Speed Limit for Imaginary-Time Schrödinger Equation with Application to Quantum Searches

Jie Sun, Songfeng Lu

Recently, Okuyama and Ohzek [1] derived a speed limit for the imaginary-time Schrödinger equation, which is inspired by the prior work of Kieu, who had shown a new class of time–energy uncertainty relations suitable for actually evaluating the speed limit of quantum dynamics. In this paper, we apply the result of Okuyama and Ohzek to obtain a generalized speed limit for Grover’s search in imaginary-time quantum annealing. An estimate of the lower bound on the computational time is shown, from which the role of the coefficient function corresponding to the final Hamiltonian played in the quantum dynamics for the problem is sticking out. However, when trying to apply the speed limit to the analogue of Grover’s problem, we find that not only the coefficient of the target Hamiltonian is related to the time complexity of the algorithm, but also the coefficient of the initial Hamiltonian is crucial for determining the time complexity. This is new and generalizes one of the results in our previous work.

Open Systems & Information Dynamics•Jun 1, 2021•0 citations

On the time-independent Hamiltonian in real-time and imaginary-time quantum annealing*

Jie Sun, Songfeng Lu

We present the analog analogue of Grover’s problem as an example of the time-independent Hamiltonian for applying the speed limit of the imaginary-time Schrödinger equation derived by Okuyama and Ohzeki and the new class of energy-time uncertainty relation proposed by Kieu. It is found that the computational time of the imaginary-time quantum annealing of this Grover search can be exponentially small, while the counterpart of the quantum evolution driven by the real-time Schrödinger equation could only provide square root speedup, compared with classic search. The present results are consistent with the cases of the time-dependent quantum evolution of the natural Grover problem in previous works. We once again emphasize that the logarithm and square root algorithmic performances are generic in imaginary-time quantum annealing and quantum evolution driven by real-time Schrödinger equation, respectively. Also, we provide evidences to search deep reasons why the imaginary-time quantum annealing can lead to exponential speedup and the real-time quantum annealing can make square root speedup.

Chinese Physics B•Jul 6, 2020•7 citations

A useful fundamental speed limit for the imaginary-time Schrodinger equation

Manaka Okuyama, Masayuki Ohzeki

The quantum speed limit (QSL), or the energy-time uncertainty relation, gives a fundamental speed limit for quantum dynamics. Recently, Kieu [arXiv:1702.00603] derived a new class of QSL which is not only formal but also suitable for actually evaluating the speed limit. Inspired by his work, we obtain a similar speed limit for the imaginary-time Schrödinger equation. Using this new bound, we show that the optimal computational time of the Grover problem in imaginary-time quantum annealing is bounded from below by $\log N$, which is consistent with a result of previous study.

arXiv:1806.09040•Jun 23, 2018•0 citations

A class of time-energy uncertainty relations for time-dependent Hamiltonians

Tien D. Kieu

A new class of time-energy uncertainty relations is directly derived from the Schrödinger equations for time-dependent Hamiltonians. Only the initial states and the Hamiltonians, but neither the instantaneous eigenstates nor the full time-dependent wave funct- ions, which would demand a full solution for a time-dependent Hamiltonian, are required for our time-energy relations. Explicit results are then presented for particular subcases of interest for time-independent Hamiltonians and also for time-varying Hamiltonians employed in adiabatic quantum computation. Some estimates of the lower bounds on computational time are given for general adiabatic quantum algorithms, with Grover's search as an illustration. We particularly emphasize the role of required energy resources, besides the space and time complexity, for the physical process of (quantum) computation, in general.

arXiv:1702.00603•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jun 1, 2019•12 citations

A Refined Speed Limit for the Imaginary-Time Schrödinger Equation

Jie Sun, Songfeng Lu

Recently, Kieu proposed a new class of time-energy uncertainty relations for time-dependent Hamiltonians, which is not only formal but also useful for actually evaluating the speed limit of quantum dynamics. Inspired by this work, Okuyama and Ohzeki obtained a similar speed limit for the imaginary-time Schrödinger equation. In this paper, we refine the latter one to make it be further like that of Kieu formally. As in the work of Kieu, only the initial states and the Hamiltonians, but neither the instantaneous eigenstates nor the full time-dependent wave like functions, which would demand a full solution for a time-dependent system, are required for our optimized speed limit. It turns out to be more helpful for estimating the speed limit of an actual quantum annealing driven by the imaginary-time Schrödinger equation. For certain case, the refined speed limit given here becomes the only useful tool to do this estimation, because the one given by Okuyama and Ohzeki cannot do the same job.

Open Systems & Information Dynamics•Jun 1, 2020•0 citations

On the General Class of Models of Adiabatic Evolution

Jie Sun, Songfeng Lu, Fang Liu

The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.

Open Systems & Information Dynamics•Sep 1, 2016•3 citations
Recently, Kieu derived a new class of time–energy uncertainty relations, which is not only formal but also suitable for evaluating the speed limit of quantum dynamics. However, when this time–energy uncertainty relation was applied to study the quantum adiabatic Grover’s search, some approximation had been done for reaching the right conclusion. That is, the final state being orthogonal to the initial state in this problem was assumed which may cause confusion, while the truth is that the overlap between these two states is indeed very small when the problem size is very big but not equal to zero exactly. In this paper, we modify the time–energy uncertainty relation of Kieu applied to two quantum evolutions of Grover’s problem, and find that the resulting computational complexities match well with the previous works on this topic but without the need of making the assumption like that in the work of Kieu.
Recently, Okuyama and Ohzek [1] derived a speed limit for the imaginary-time Schrödinger equation, which is inspired by the prior work of Kieu, who had shown a new class of time–energy uncertainty relations suitable for actually evaluating the speed limit of quantum dynamics. In this paper, we apply the result of Okuyama and Ohzek to obtain a generalized speed limit for Grover’s search in imaginary-time quantum annealing. An estimate of the lower bound on the computational time is shown, from which the role of the coefficient function corresponding to the final Hamiltonian played in the quantum dynamics for the problem is sticking out. However, when trying to apply the speed limit to the analogue of Grover’s problem, we find that not only the coefficient of the target Hamiltonian is related to the time complexity of the algorithm, but also the coefficient of the initial Hamiltonian is crucial for determining the time complexity. This is new and generalizes one of the results in our previous work.
We present the analog analogue of Grover’s problem as an example of the time-independent Hamiltonian for applying the speed limit of the imaginary-time Schrödinger equation derived by Okuyama and Ohzeki and the new class of energy-time uncertainty relation proposed by Kieu. It is found that the computational time of the imaginary-time quantum annealing of this Grover search can be exponentially small, while the counterpart of the quantum evolution driven by the real-time Schrödinger equation could only provide square root speedup, compared with classic search. The present results are consistent with the cases of the time-dependent quantum evolution of the natural Grover problem in previous works. We once again emphasize that the logarithm and square root algorithmic performances are generic in imaginary-time quantum annealing and quantum evolution driven by real-time Schrödinger equation, respectively. Also, we provide evidences to search deep reasons why the imaginary-time quantum annealing can lead to exponential speedup and the real-time quantum annealing can make square root speedup.
The quantum speed limit (QSL), or the energy-time uncertainty relation, gives a fundamental speed limit for quantum dynamics. Recently, Kieu [arXiv:1702.00603] derived a new class of QSL which is not only formal but also suitable for actually evaluating the speed limit. Inspired by his work, we obtain a similar speed limit for the imaginary-time Schrödinger equation. Using this new bound, we show that the optimal computational time of the Grover problem in imaginary-time quantum annealing is bounded from below by log⁡N\log NlogN, which is consistent with a result of previous study.
A new class of time-energy uncertainty relations is directly derived from the Schrödinger equations for time-dependent Hamiltonians. Only the initial states and the Hamiltonians, but neither the instantaneous eigenstates nor the full time-dependent wave funct- ions, which would demand a full solution for a time-dependent Hamiltonian, are required for our time-energy relations. Explicit results are then presented for particular subcases of interest for time-independent Hamiltonians and also for time-varying Hamiltonians employed in adiabatic quantum computation. Some estimates of the lower bounds on computational time are given for general adiabatic quantum algorithms, with Grover's search as an illustration. We particularly emphasize the role of required energy resources, besides the space and time complexity, for the physical process of (quantum) computation, in general.
Recently, Kieu proposed a new class of time-energy uncertainty relations for time-dependent Hamiltonians, which is not only formal but also useful for actually evaluating the speed limit of quantum dynamics. Inspired by this work, Okuyama and Ohzeki obtained a similar speed limit for the imaginary-time Schrödinger equation. In this paper, we refine the latter one to make it be further like that of Kieu formally. As in the work of Kieu, only the initial states and the Hamiltonians, but neither the instantaneous eigenstates nor the full time-dependent wave like functions, which would demand a full solution for a time-dependent system, are required for our optimized speed limit. It turns out to be more helpful for estimating the speed limit of an actual quantum annealing driven by the imaginary-time Schrödinger equation. For certain case, the refined speed limit given here becomes the only useful tool to do this estimation, because the one given by Okuyama and Ohzeki cannot do the same job.
The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use.