Can I read A Theory of Quantum Differential Equation Solvers: Limitations and Fast-forwarding on EtoBox?

A Theory of Quantum Differential Equation Solvers: Limitations and Fast-forwarding by An, Dong; Liu, Jin-Peng; Wang, Daochen; Zhao, Qi is a scholarly article available to read on EtoBox.

What is A Theory of Quantum Differential Equation Solvers: Limitations and Fast-forwarding about?

We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic homogeneous linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of ``non-quantumness'': real part gap and non-normality of the coefficient matrix. We then show that homogeneous ODEs in the absence of both types of ``non-quantumness'' are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. We generalize our results to the inhomogeneous case and find that existing generic quantum ODE solvers cannot be substantially improved. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved ef

Author

An, Dong; Liu, Jin-Peng; Wang, Daochen; Zhao, Qi

Published

2022

Language

EN