Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound

Abstract

Digital quantum simulation has broad applications in approximating unitary evolution of Hamiltonians. In practice, many simulation tasks for quantum systems focus on quantum states in the low-energy subspace instead of the entire Hilbert space. In this paper, we systematically investigate the complexity of digital quantum simulation based on product formulas in the low-energy subspace. We show that the simulation error depends on the effective low-energy norm of the Hamiltonian for a variety of digital quantum simulation algorithms and quantum systems, allowing improvements over the previous complexities for full unitary simulations even for imperfect state preparations due to thermalization. In particular, for simulating spin models in the low-energy subspace, we prove that randomized product formulas such as qDRIFT and random permutation require smaller Trotter numbers. Such improvement also persists in symmetry-protected digital quantum simulations. We prove a similar improvement in simulating the dynamics of power-law quantum interactions. We also provide a query lower bound for general digital quantum simulations in the low-energy subspace.

arXiv comment34 pages, 4 figures, github repo: https://github.com/Qubit-Fernand/Digital-Quantum-Simulation

References in corpus (22)

• Quantum Computing in the NISQ era and beyond
• Quantum Simulation
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Toward the first quantum simulation with quantum speedup
• A Theory of Trotter Error
• A random compiler for fast Hamiltonian simulation
• Exponential improvement in precision for simulating sparse Hamiltonians
• A Limit on the Speed of Quantum Computation in Determining Parity
• Nearly optimal lattice simulation by product formulas
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Algorithms for quantum simulation at finite energies
• Hamiltonian simulation in the low-energy subspace
• Faster Digital Quantum Simulation by Symmetry Protection
• Connecting global and local energy distributions in quantum spin models on a lattice
• Hamiltonian simulation with random inputs
• How much entanglement is needed to reduce the energy variance?
• State-dependent Trotter Limits and their approximations
• Average-case Speedup for Product Formulas
• Doubling the order of approximation via the randomized product formula

Cited by in corpus (4)

• Strong Error Bounds for Trotter & Strang-Splittings and Their Implications for Quantum Chemistry
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Hamiltonian simulation for low-energy states with optimal time dependence
• Trotterization is substantially efficient for low-energy states