Quantum algorithm speeds up simulating open quantum systems efficiently
Query-Optimal and Gate-Efficient Lindbladian Simulation
Data Structures and Algorithms
Summary
Simulating how quantum systems interact with their environments is a key challenge in quantum computing. The authors present a new quantum algorithm that simulates these open quantum systems with optimal query efficiency and fewer computational gates. Their approach uses clever encoding methods and approximations to accurately mimic the system’s evolution while balancing accuracy and computational cost. This makes such simulations potentially more practical on future quantum devices.
What this means in practice
- •For quantum hardware engineers: Implement more efficient control algorithms for simulating open quantum system dynamics on quantum processors, reducing computational resource usage.
- •For quantum software developers: Develop optimized quantum simulation software that leverages query-optimal Lindbladian simulation for better accuracy and lower gate counts in noisy intermediate-scale quantum devices.
Authors
Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou
Abstract
We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian $H$ and a projected unitary encoding of the stacked jump operator $B=\sum_{k=1}^m \lvert k\rangle\otimes L_k$, with normalization factors $α_H$ and $α_B$, respectively. For evolution time $t$, set $τ=(α_H+α_B^2)t$. The algorithm approximates the evolution channel to diamond-norm error $\varepsilon$ using $O\!\left(τ+\frac{\log(1/\varepsilon)}{\log\!\left(e+\log(1/\varepsilon)/τ\right)}\right)$ oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.