On the commutator scaling in Hamiltonian simulation with multi-product formulas

Abstract

A multi-product formula (MPF) is a promising approach for Hamiltonian simulation efficiently both in the system size $N$ and the inverse allowable error $1/\epsilon$ by combining Trotterization and the linear combination of unitaries (LCU). It achieves poly-logarithmic cost in $1/\epsilon$ like LCU [G. H. Low, V. Kliuchnikov, N. Wiebe, arXiv:1907.11679 (2019)]. The efficiency in $N$ is expected to come from the commutator scaling in Trotterization, and this appears to be confirmed by the error bound of MPF expressed by nested commutators [J. Aftab, D. An, K. Trivisa, arXiv:2403.08922 (2024)]. However, we point out that the efficiency of MPF in the system size $N$ is not exactly resolved yet in that the present error bound expressed by nested commutators is incompatible with the size-efficient complexity reflecting the commutator scaling. The problem is that $q$-fold nested commutators with arbitrarily large $q$ are involved in their requirement and error bound. The benefit of commutator scaling by locality is absent, and the cost efficient in $N$ becomes prohibited in general. In this paper, we show an alternative commutator-scaling error of MPF and derive its size-efficient cost properly inheriting the advantage in Trotterization. The requirement and the error bound in our analysis, derived by techniques from the Floquet-Magnus expansion, have a certain truncation order in the nested commutators and can fully exploit the locality. We prove that Hamiltonian simulation by MPF certainly achieves the cost whose system-size dependence is as large as Trotterization while keeping the $\mathrm{polylog}(1/\epsilon )$-scaling like the LCU. Our results will provide improved or accurate error and cost also for various algorithms using interpolation or extrapolation of Trotterization.

31 pages, 1 table

References in corpus (26)

• Quantum Amplitude Amplification and Estimation
• The Magnus expansion and some of its applications
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Equilibrium states of generic quantum systems subject to periodic driving
• Long-time behavior of periodically driven isolated interacting lattice systems
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• A Theory of Trotter Error
• Floquet-Magnus Theory and Generic Transient Dynamics in Periodically Driven Many-Body Quantum Systems
• Exponentially slow heating in periodically driven many-body systems
• Rigorous Bound on Energy Absorption and Generic Relaxation in Periodically Driven Quantum Systems
• Effective Hamiltonians, prethermalization and slow energy absorption in periodically driven many-body systems
• A Rigorous Theory of Many-Body Prethermalization for Periodically Driven and Closed Quantum Systems
• Nearly optimal lattice simulation by product formulas
• Quantum algorithm for simulating real time evolution of lattice Hamiltonians
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Locality and digital quantum simulation of power-law interactions
• Mitigating algorithmic errors in Hamiltonian simulation
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Randomizing multi-product formulas for Hamiltonian simulation
• A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation
• Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation
• Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
• Trotterization is substantially efficient for low-energy states
• Unifying framework for quantum simulation algorithms for time-dependent Hamiltonian dynamics

Cited by in corpus (1)

• Tensor-based phase difference estimation on time series analysis