Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation

• URL: http://arxiv.org/abs/2608.30629v1
• Date: Mon, 31 Aug 2026 11:39:55 GMT
• Title: Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation
• Abstract summary: 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
• Score: 17.156227790252526
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The query-optimal algorithm of [CGWZ26] for general time-dependent Hamiltonian simulation uses $$ q = O\left( αT + \frac{\log(1/\varepsilon)}{\log\left(e + \log(1/\varepsilon)/(αT) \right)} \right) $$ queries to $\mathrm{HAM\mbox{-}T}$ within $\varepsilon$ error for a Lipschitz-continuous time-dependent Hamiltonian $H(t)$ on $[0,T]$ satisfying $\left\lVert H(t)\right\rVert\leqα$. However, its direct circuit implementation incurs a substantially larger gate overhead. In this note, we give an implementation of the same algorithm that retains its optimal query complexity and uses $$ O\left[ q \left( a + \log\left(1 + \frac{T(α+ βT)}{\varepsilon} \right) \right) \right] $$ one- and two-qubit gates, where $a$ is the number of block-encoding ancilla qubits and $β$ is the Lipschitz constant of $H$. The main ingredient is an exact dyadic factorization of the ordered update product in the underlying one-query transducer.

Related papers

• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• 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)
• Time-Dependent Hamiltonian Simulation with Optimal Query Complexity [7.005823894951329]
  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.
  arXiv  Detail & Related papers  (2026-08-06T14:35:47Z)
• 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)
• Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Model [37.35522173770848]
  John ellipsoid of symmetric polytope $P=mathbfxinmathbbRd:|mathbfAmathbfx|_inftyle1$, $mathbfAinmathbbRntimes d$, is computed by a long line of leverage-score algorithms.
  arXiv  Detail & Related papers  (2026-06-18T11:00:03Z)
• 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)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  We study first-order methods for convex optimization problems with functions $f$ satisfying the recently proposed $ell$-smoothness condition $||nabla2f(x)|| le ellleft(||nabla f(x)||right),$ which generalizes the $L$-smoothness and $(L_0,L_1)$-smoothness.
  arXiv  Detail & Related papers  (2025-08-09T08:28:06Z)
• 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)
• Almost Optimal Proper Learning and Testing Polynomials [0.11421942894219898]
  Our algorithm makes $$q_U=left(fracsepsilonright)fraclog betabeta+O(frac1beta)+ tilde Oleft(logfrac1epsilonright)log n,$$. All previous algorithms have query complexity at least quadratic in $s$ and linear in $1/epsilon$.
  arXiv  Detail & Related papers  (2022-02-07T14:15:20Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  We prove that an optimistic $Q$-learning enjoys a $mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, $T$ is the total number of steps, and $Delta_min$ is the minimum sub-optimality gap.
  arXiv  Detail & Related papers  (2020-06-16T13:01:33Z)
• Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
  We give a sharp complexity analysis for EXTRA with the improved $Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$. Our communication complexities of the accelerated EXTRA are only worse by the factors of $left(logfracLmu (1-sigma_2(W))right)$ and $left(logfrac1epsilon (1-
  arXiv  Detail & Related papers  (2020-02-24T08:07:08Z)
• 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.