Diagonal-Budgeted Trotterization for Efficient Quantum Hamiltonian Simulation

Abstract

Efficient classical simulation of quantum Hamiltonian dynamics is often bottlenecked by exponential state growth and the overhead of generic sparse linear algebra. We introduce diagonal-budgeted Trotterization, a structure-aware strategy that decomposes Hamiltonians into factors preserving diagonal sparsity while tightly controlling fidelity loss. Our implementation, HamSim, utilizes a compact diagonal-sparse data layout and specialized C++/CUDA kernels to bypass the overheads of generic formats like CSR. By leveraging SIMD vectorization, multithreading, and GPU acceleration, HamSim achieves high performance across heterogeneous architectures. Benchmarks on the HamLib suite show that HamSim significantly outperforms Qiskit-Aer. On CPUs, HamSim attains speedups of $182$--$1,269\times$ on optimization instances (TSP, MaxCut) and $4.8$--$841\times$ on physical models (TFIM, Heisenberg). On GPUs, it achieves up to $178\times$ speedup for $12$--$16$ qubit problems. Unlike traditional Trotterization, HamSim maintains near-perfect fidelity without requiring exponential steps. This demonstrates that diagonal-aware numerical kernels provide a scalable foundation for high-fidelity classical Hamiltonian simulation.

Extended version including appendix. Accepted to ACM ICS 2026

References in corpus (19)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Array Programming with NumPy
• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• QuTiP: An open-source Python framework for the dynamics of open quantum systems
• Hamiltonian Simulation by Qubitization
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Toward the first quantum simulation with quantum speedup
• Quantum Risk Analysis
• QuEST and High Performance Simulation of Quantum Computers
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Exponential improvement in precision for simulating sparse Hamiltonians
• Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Optimised Trotter Decompositions for Classical and Quantum Computing
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Measuring Trotter error and its application to precision-guaranteed Hamiltonian simulations