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

arXiv:quant-ph/0511245 · Physical Review A

Elementary proof of the bound on the speed of quantum evolution

Piotr Kosiński, Magdalena Zych

Published Feb 14, 2006• 28 citations
arXivHTMLPDF

Abstract

An elementary proof is given of the bound on "ortogonalization time".
DOI
10.1103/physreva.73.024303

Related papers

α>(ε)=α<(ε) for the Margolus-Levitin quantum speed limit bound

H. F. Chau

The Margolus-Levitin (ML) bound says that for any time-independent Hamiltonian, the time needed to evolve from one quantum state to another is at least $\ensuremath{\pi}\ensuremath{\alpha}(\ensuremath{\epsilon})/2\ensuremath{\langle}E\ensuremath{-}{E}_{0}\ensuremath{\rangle}$, where $\ensuremath{\langle}E\ensuremath{-}{E}_{0}\ensuremath{\rangle}$ is the expected energy of the system relative to the ground state of the Hamiltonian and $\ensuremath{\alpha}(\ensuremath{\epsilon})$ is a function of the fidelity $\ensuremath{\epsilon}$ between the two states. For a long time, only an upper bound ${\ensuremath{\alpha}}_{>}(\ensuremath{\epsilon})$ and a lower bound ${\ensuremath{\alpha}}_{<}(\ensuremath{\epsilon})$ are known, although they agree up to at least seven significant figures. Recently, H\"ornedal and S\"onnerborn [arXiv:2301.10063] proved an analytical expression for $\ensuremath{\alpha}(\ensuremath{\epsilon})$, a fully classified system whose evolution time saturates the ML bound, and gave this bound a symplectic-geometric interpretation. Here I solve the same problem through an elementary proof of the ML bound. By explicitly finding all the states that saturate the ML bound, I show that ${\ensuremath{\alpha}}_{>}(\ensuremath{\epsilon})$ is indeed equal to ${\ensuremath{\alpha}}_{<}(\ensuremath{\epsilon})$. More importantly, I point out a numerical stability issue in computing ${\ensuremath{\alpha}}_{>}(\ensuremath{\epsilon})$ and report a simple way to evaluate it efficiently and accurately.

arXiv:2305.10101•Physical Review A•Nov 1, 2023•4 citations

An Estimate of Quantum Evolution Speed.

Shuangshuang Fu

International Journal of Software and Informatics•Jan 1, 2014•0 citations

Optimal Lower Bounds for Hamiltonian Simulation

Alexander Zlokapa, Richard R. Allen, Aram W. Harrow

For Hamiltonian $H = \sum_j h_j$, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms $\|h_j\|$, time $t$, and trace-distance error $ε$. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case $\|h_j\|$ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in $1/ε$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.

quant-pharXiv:2607.19852•Jul 23, 2026•2 citations

Quantum Adiabatic Theorem Revisited

Runyao Duan

In 2004 Ambainis and Regev formulated a certain form of quantum adiabatic theorem and provided an elementary proof which is especially accessible to computer scientists. Their result is achieved by discretizing the total adiabatic evolution into a sequence of unitary transformations acting on the quantum system. Here we continue this line of study by providing another elementary and shorter proof with improved bounds. Our key finding is a succinct integral representation of the difference between the target and the actual states, which yields an accurate estimation of the approximation error. Our proof can be regarded as a "continuous" version of the work by Ambainis and Regev. As applications, we show how to adiabatically prepare an arbitrary qubit state from an initial state.

arXiv:2003.03063•Mar 6, 2020•6 citations

Some remarks on quantum speed limit for n-dimensional systems

Ho Minh Toan, Manh Cuong Tran, Vu The Khoi

Quantum Information Processing•Feb 12, 2026•0 citations

Elementary proofs of quantum lower bounds for element distinctness and k-sum

Andris Ambainis, Martins Kokainis

We give elementary proofs of the $Ω(n^{2/3})$ quantum query lower bound for element distinctness and the $Ω(n^{k/(k+1)})$ lower bound for the $k$-sum problem, for fixed $k$ and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.

quant-pharXiv:2610.32693•Oct 26, 2026•0 citations
The Margolus-Levitin (ML) bound says that for any time-independent Hamiltonian, the time needed to evolve from one quantum state to another is at least $\ensuremath{\pi}\ensuremath{\alpha}(\ensuremath{\epsilon})/2\ensuremath{\langle}E\ensuremath{-}{E}_{0}\ensuremath{\rangle}$, where $\ensuremath{\langle}E\ensuremath{-}{E}_{0}\ensuremath{\rangle}$ is the expected energy of the system relative to the ground state of the Hamiltonian and $\ensuremath{\alpha}(\ensuremath{\epsilon})$ is a function of the fidelity $\ensuremath{\epsilon}$ between the two states. For a long time, only an upper bound ${\ensuremath{\alpha}}_{>}(\ensuremath{\epsilon})$ and a lower bound ${\ensuremath{\alpha}}_{<}(\ensuremath{\epsilon})$ are known, although they agree up to at least seven significant figures. Recently, H\"ornedal and S\"onnerborn [arXiv:2301.10063] proved an analytical expression for $\ensuremath{\alpha}(\ensuremath{\epsilon})$, a fully classified system whose evolution time saturates the ML bound, and gave this bound a symplectic-geometric interpretation. Here I solve the same problem through an elementary proof of the ML bound. By explicitly finding all the states that saturate the ML bound, I show that ${\ensuremath{\alpha}}_{>}(\ensuremath{\epsilon})$ is indeed equal to ${\ensuremath{\alpha}}_{<}(\ensuremath{\epsilon})$. More importantly, I point out a numerical stability issue in computing ${\ensuremath{\alpha}}_{>}(\ensuremath{\epsilon})$ and report a simple way to evaluate it efficiently and accurately.
For Hamiltonian H=∑jhjH = \sum_j h_jH=∑j​hj​, we prove asymptotically tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer. Our bounds hold for arbitrary term norms ∥hj∥\|h_j\|∥hj​∥, time ttt, and trace-distance error εεε. The matching upper bound (known as composite qDRIFT) consists of high-order Trotterization of the large terms and a randomized first-order Trotterization of the small terms. Unlike prior work that chooses worst-case ∥hj∥\|h_j\|∥hj​∥ to encode the computation of parity or other Boolean functions in time evolution, our proof is elementary and based on a local, bounded-degree classical Hamiltonian. Our work suggests that for many physical systems (e.g., power-law interactions), gate count must scale polynomially in 1/ε1/ε1/ε, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
In 2004 Ambainis and Regev formulated a certain form of quantum adiabatic theorem and provided an elementary proof which is especially accessible to computer scientists. Their result is achieved by discretizing the total adiabatic evolution into a sequence of unitary transformations acting on the quantum system. Here we continue this line of study by providing another elementary and shorter proof with improved bounds. Our key finding is a succinct integral representation of the difference between the target and the actual states, which yields an accurate estimation of the approximation error. Our proof can be regarded as a "continuous" version of the work by Ambainis and Regev. As applications, we show how to adiabatically prepare an arbitrary qubit state from an initial state.
We give elementary proofs of the Ω(n2/3)Ω(n^{2/3})Ω(n2/3) quantum query lower bound for element distinctness and the Ω(nk/(k+1))Ω(n^{k/(k+1)})Ω(nk/(k+1)) lower bound for the kkk-sum problem, for fixed kkk and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.