arXiv:2610.01839
Toward Optimal Circuit Depth for Geometrically Local Hamiltonian Simulation
Zheyu Shen, Yusen Wu, Penghui Yao, Xiao Yuan, Yukun Zhang
Abstract
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy $ε$, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an $n$-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time $T\ge1$, with circuit depth $O(T\log(nT/ε))$ and gate count $O(nT\log(nT/ε))$. This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization. Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time $T$ in the stated regime and sufficiently small fixed error $ε$, any nearest-neighbor quantum circuit simulating these dynamics requires depth $Ω(\log n/\log\log n)$. This matches our $O(\log n)$ upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.
AI Summary
The paper asks how much circuit-depth overhead is required to simulate geometrically local Hamiltonian dynamics at global operator-norm accuracy. For time-independent, finite-range Hamiltonians on fixed-dimensional lattices, with normalized local interaction strength and $T\ge1$, it constructs nearest-neighbor circuits with depth $O(T\log(nT/\epsilon))$, gate count $O(nT\log(nT/\epsilon))$, and $O(n)$ ancillas at bounded density. This replaces the polylogarithmic overhead in the HHKL simulation framework with a single logarithm. The construction retains HHKL’s Lieb–Robinson decomposition into blocks of diameter $M=\Theta(\log(nT/\epsilon))$. Each short-time block evolution is approximated to error $e^{-M}$ in depth $O(M)$. A fixed-order product formula, with even order $p>D$, leaves a correction whose absolute coefficient sum is controlled by the block volume. An interleaved LCU expansion supplies exponential accuracy while retaining bounded-support insertions. Independently prepared labels, reversible coefficient processing, and pipelined geometric control distribution implement the correction; one oblivious-amplification step controls the complete output, including ancillary error. An unconditional lower bound for uniform nearest-neighbor XXZ dynamics gives depth $\Omega(\log n/\log\log n)$ at fixed time and sufficiently small fixed error. It combines weak excitation-arrival signals across separated reference regions and controls their difference from the interacting evolution. A joint bound has additive time and precision terms, leaving a larger gap for growing time. The upper bound assumes sufficiently long lattice sides and arbitrary exact single-qubit gates. Finite-gate-set synthesis adds overhead; numerical preprocessing is not assigned a representation-independent cost. Short lattice sides and time-dependent interactions are not covered.
The proofs and manuscript were developed through multiple rounds of interaction between the authors and GPT-5.6 and GPT-6, which assisted with calculations, proof development, and writing.
Error found: The abstract states the upper bound without the minimum-side-length condition required by the global theorem, so the proved result covers a narrower range of lattice geometries and target accuracies.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 71 pages, 8 figures