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=∑jhj, 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∥, 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 ∥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/ε, 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) quantum query lower bound for element distinctness and the Ω(nk/(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.