This work suggests that for many physical systems, gate count must scale polynomially in $1/\epsilon$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
Abstract
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 $\epsilon$. 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/\epsilon$, contrary to the complexity suggested by counting coherent oracle queries such as those in the block-encoding model.
We give a quantum algorithm for simulating a $d$-sparse Hermitian Hamiltonian $H$, assuming a known upper bound $\Lambda$ on its maximum column Euclidean norm $\|H\|_{1\to2}$. For $t\Lambda\ge1/2$, simulation with operator-norm error $\epsilon$ uses \[ O\!\left(t\Lambda\sqrt d+\sqrt d\log(2/\epsilon)\right) \] sparse-o...
Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $\delta$. Quantum singular value transformation gives an upper bound of $O\!\left(\fr...
A. Liu, Adam Wesolowski, Jayne Thompson et al.· 0 citations
We give a query-optimal algorithm for simulating a general $n$-qubit time-dependent Hamiltonian $H(t)$ on $[0,T]$, assuming that $H$ is Lipschitz continuous and $\|H(t)\|\leq\alpha$. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator $U_H(T)$ to error $\varepsil...
Bo-Yang Chen, Min-Bo Gao, Xin-Zhao Wang et al.· 8 citations· ⚡2
Product formulas, also known as Trotter formulas, are among the most widely used and practical methods for simulating quantum systems on quantum computers. Here we introduce two new classes of randomized product formulas for simulating Hamiltonians with separated energy scales, $H=A+\alpha B$, where $\alpha$ is small....
Leeseok Kim, Luis Pedro Garc'ia-Pintos· 2 citations· ⚡1
How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function $f:[N]\to [N]$, the BHT algorithm finds a collision using $O(N^{1/3})$ queries and a quantumly accessible classical table containing $O(N^{1/3})$ input-output pairs, whereas a logarithmic-space Grover search u...
We develop a quantum algorithm for slow analytic Hamiltonians $\widetilde H(t)=H(t/T)$ with $\|H(s)\|\leq\alpha$ that achieves nearly additive query complexity and low gate overhead. Our main technical contribution is a periodic Gevrey extension of $H(s)$, together with Fourier component decay and truncation bounds tha...
Chen Zhao, Yinan Li, Dong An· 3 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
