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.
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.
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.
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.