Time-Dependent Hamiltonian Simulation with Optimal Query Complexity

• URL: http://arxiv.org/abs/2608.06094v1
• Date: Thu, 06 Aug 2026 14:35:47 GMT
• Title: Time-Dependent Hamiltonian Simulation with Optimal Query Complexity
• Abstract summary: We give a query-optimal algorithm for simulating a general $n$-qubit time-dependent Hamiltonian $H(t)$ on $[0,T]$.<n>A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially.<n>For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.
• Score: 7.005823894951329
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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α$. In the standard $\mathrm{HAM\mbox{-}T}$ access model, the algorithm approximates the time-ordered propagator $U_H(T)$ to error $\varepsilon$ using $$ O\left( αT+\frac{\log(1/\varepsilon)} {\log(e+\log(1/\varepsilon)/(αT))} \right) $$ $\mathrm{HAM\mbox{-}T}$ queries. This matches the known query lower bound for time-independent Hamiltonians, showing that time dependence incurs no asymptotic query overhead. Our method first constructs a one-query transducer that, given an auxiliary state, implements an approximation to $U_H(T)$ and returns the state unchanged. A weighted combination of circuits that apply the transducer different numbers of times makes the error caused by omitting this state decay factorially, yielding the stated optimal precision dependence. For time-independent Hamiltonians, the same method also gives a query-optimal alternative to qubitization.

Related papers

• Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation [17.156227790252526]
  The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = Oleft( T + fraclog (1/varepsilon)logleft(e + log (1/varepsilon)/(T) right)<n>We give an implementation of the same algorithm that retains its optimal query complexity and uses $$ Oleft[ q left( a + logleft (1 + fracT(+ T)varepsilon
  arXiv  Detail & Related papers  (2026-08-31T11:39:55Z)
• Quantum simulation of slow analytic time-dependent Hamiltonians [10.542661137364275]
  We develop a quantum algorithm for slow analytic Hamiltonians $widetilde H(t)=H(t/T)$ with $|H(s)|leq$ that achieves nearly additive query complexity and low gate overhead.
  arXiv  Detail & Related papers  (2026-08-18T11:14:53Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing [0.0]
  We find the anti-Hermitian query complexity $d_I = (betaI T + log/varepsilon)/loglog (1/varepsilon)$ to be tight, established via Chebyshev coefficient, modified Bessel functions, and Lambert$W$ inversion.<n>A constant-access-operator construction achieves intrinsic barrier $e-2T$ on a restricted domain, though extension to the full bitorus remains open.
  arXiv  Detail & Related papers  (2026-05-12T19:03:36Z)
• Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties [3.3728077347699497]
  We investigate Lindbladian fast-forwarding and its applications to estimating Gibbs state properties.<n>Fast-forwarding refers to the ability to simulate a system of time $t$ using significantly fewer than $t$ queries or circuit depth.
  arXiv  Detail & Related papers  (2025-09-11T14:57:53Z)
• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  We study the estimation of relative entropy $D(rho|sigma)$ when $sigma$ is known.<n>Our estimator attains the Cram'er-Rao type bound when the dimension $d$ is fixed.
  arXiv  Detail & Related papers  (2024-06-25T06:07:20Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states [0.9453554184019105]
  We show how to learn the coefficients of a Hamiltonian to error $varepsilon$ with sample complexity $S = O(log N/(betavarepsilon)2)$ and time linear in the sample size, $O(S N)$. In the appendix, we show virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e-it Hilon in a small $t regime with similar sample and time complexity.
  arXiv  Detail & Related papers  (2021-08-10T18:00:49Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.