Well-conditioned multiproduct Hamiltonian simulation

2019/07/26 by Guang Hao Low, Vadym Kliuchnikov, Low, Guang Hao +3 · 5 citations
Computer Science · #Computational Physics (physics.comp-ph) #FOS: Physical sciences #Matrix Theory and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.1907.11679

openalex publication_date 2019/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Product formula approximations of the time-evolution operator on quantum computers are of great interest due to their simplicity, and good scaling with system size by exploiting commutativity between Hamiltonian terms. However, product formulas exhibit poor scaling with the time t and error ε of simulation as the gate cost of a single step scales exponentially with the order m of accuracy. We introduce well-conditioned multiproduct formulas, which are a linear combination of product formulas, where a single step has polynomial cost O(m²log(m)) and succeeds with probability Ω(1/log²(m)). Our multiproduct formulas imply a simple and generic simulation algorithm that simultaneously exploits commutativity in arbitrary systems and has a worst-case cost O(tlog²(t/ε)) which is optimal up to poly-logarithmic factors. In contrast, prior Trotter and post-Trotter Hamiltonian simulation algorithms realize only one of these two desirable features. A key technical result of independent interest is our solution to a conditioning problem in previous multiproduct formulas that amplified numerical errors by e^Ω(m) in the classical setting, and led to a vanishing success probability e^-Ω(m) in the quantum setting.

Citations

• On the product of semi-groups of operators
• Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations
• Hamiltonian Simulation by Uniform Spectral Amplification

Cited by

• Polylogarithmic-Depth Quantum Algorithm for Simulating the Extended Hubbard Model on a Two-Dimensional Lattice Using the Fast Multipole Method
• A Monte Carlo approach to bound Trotter error
• A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz
• High-order Magnus Expansion for Hamiltonian Simulation
• Reducing Circuit Depth in Lindblad Simulation via Step-Size Extrapolation

Related

• Trotter error bounds and dynamic multi-product formulas for Hamiltonian simulation
• Multi-product Hamiltonian simulation with explicit commutator scaling
• A Rigorous Introduction to Hamiltonian Simulation via High-Order Product Formulas
• Faster Algorithmic Quantum and Classical Simulations by Corrected Product Formulas
• Beyond Trotterization: Variational Product Formulas for Quantum Simulation