Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
arXiv:2410.19628 · doi:10.1103/cvl9-97qg
Abstract
Solving linear ordinary differential equations (ODE) is one of the most promising applications for quantum computers to demonstrate exponential advantages. The challenge of designing a quantum ODE algorithm is how to embed non-unitary dynamics into intrinsically unitary quantum circuits. In this work, we propose a new quantum algorithm for solving ODEs by harnessing open quantum systems. Specifically, we propose a novel technique called non-diagonal density matrix encoding, which leverages the inherent non-unitary dynamics of Lindbladians to encode general linear ODEs into the non-diagonal blocks of density matrices. This framework enables us to design quantum algorithms with both theoretical simplicity and high performance. Combined with the state-of-the-art quantum Lindbladian simulation algorithms, our algorithm can outperform all existing quantum ODE algorithms and achieve near-optimal dependence on all parameters under a plausible input model. We also give applications of our algorithm including the Gibbs state preparations and the partition function estimations.
8+11 pages, 1 figure, and 1 table. PRL version
References in corpus (44)
- Quantum algorithm for solving linear systems of equations
- Making Sense of Non-Hermitian Hamiltonians
- Edge states and topological invariants of non-Hermitian systems
- Exceptional Topology of Non-Hermitian Systems
- Non-Hermitian Physics
- Topological phases of non-Hermitian systems
- Symmetry and Topology in Non-Hermitian Physics
- 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
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Non-Hermitian skin effect and chiral damping in open quantum systems
- A Straightforward Introduction to Continuous Quantum Measurement
- Non-Hermitian Topology and Exceptional-Point Geometries
- Symmetries and conserved quantities in Lindblad master equations
- Quantum exceptional points of non-Hermitian Hamiltonians and Liouvillians: The effects of quantum jumps
- On the relationship between continuous- and discrete-time quantum walk
- High-order quantum algorithm for solving linear differential equations
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- Iterative Quantum Amplitude Estimation
- Loschmidt Echo
- Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
- A dissipative quantum Church-Turing theorem
- Continuous Phase Transition without Gap Closing in Non-Hermitian Quantum Many-Body Systems
- Quantum Simulation of Open Quantum Systems Using a Unitary Decomposition of Operators
- Quantum spectral methods for differential equations
- Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
- Improved quantum algorithms for linear and nonlinear differential equations
- Quantum simulation of partial differential equations via Schrodingerisation: technical details
- Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
- Time-marching based quantum solvers for time-dependent linear differential equations
- Single-ancilla ground state preparation via Lindbladians
- Simulating Open Quantum Systems Using Hamiltonian Simulations
- Non-Hermitian Hamiltonian approach to quantum transport in disordered networks with sinks: validity and effectiveness
- Topological spin excitations in non-Hermitian spin chains with a generalized kernel polynomial algorithm
- Exact solution of the Bose Hubbard model with unidirectional hopping
- Optimal state discrimination and unstructured search in nonlinear quantum mechanics
- Non-Hermitian Fermi-Dirac Distribution in Persistent Current Transport
- Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
- Quantum algorithm for time-dependent differential equations using Dyson series
- Designing open quantum systems with known steady states: Davies generators and beyond
- Quantum differential equation solvers: limitations and fast-forwarding
- Which differential equations correspond to the Lindblad equation?