Gate-Efficient Implementation of the Query-Optimal Time-Dependent Hamiltonian Simulation
2026-08-31 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors discuss a method to simulate time-dependent quantum systems with a known algorithm that requires an optimal number of queries. Although the original algorithm uses the minimum number of queries, implementing it as a quantum circuit results in many extra operations (gates). They provide a new way to build the circuit that keeps the query count optimal while significantly reducing the number of gates needed. This is achieved using a mathematical technique called dyadic factorization. Their work helps make the simulation of time-dependent quantum systems more practical.
quantum simulationtime-dependent Hamiltonianquery complexityquantum circuitsgate complexityblock encodingLipschitz continuitydyadic factorizationtransducerquantum algorithms
Authors
Boyang Chen, Minbo Gao, Zhengfeng Ji, Tongyang Li, Xinzhao Wang, Shuo Zhou
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.