Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters

Abstract

We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.

arXiv commentPublished version with newly added Section 4.4.4, updated Appendix F, and improved presentation

References in corpus (46)

• Quantum algorithm for solving linear systems of equations
• Exceptional Topology of Non-Hermitian Systems
• Quantum Amplitude Amplification and Estimation
• Topological Origin of Non-Hermitian Skin Effects
• 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
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Toward the first quantum simulation with quantum speedup
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A random compiler for fast Hamiltonian simulation
• Solving strongly correlated electron models on a quantum computer
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• High-order quantum algorithm for solving linear differential equations
• Exponential improvement in precision for simulating sparse Hamiltonians
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Nearly optimal lattice simulation by product formulas
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Faster quantum simulation by randomization
• Higher Order Decompositions of Ordered Operator Exponentials
• Continuous Phase Transition without Gap Closing in Non-Hermitian Quantum Many-Body Systems
• Quantum spectral methods for differential equations
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Improved quantum algorithms for linear and nonlinear differential equations
• A randomized quantum algorithm for statistical phase estimation
• Hamiltonian simulation in the low-energy subspace
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Quantum SDP-Solvers: Better upper and lower bounds
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Quadratic speedup for spatial search by continuous-time quantum walk
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• Time-marching based quantum solvers for time-dependent linear differential equations
• Block-encoding structured matrices for data input in quantum computing
• Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation
• Topological spin excitations in non-Hermitian spin chains with a generalized kernel polynomial algorithm
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Computing partition functions in the one clean qubit model
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra

Cited by in corpus (3)

• Divergence-free algorithms for solving nonlinear differential equations on quantum computers
• Quantum linear system algorithm with optimal queries to initial state preparation
• An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations