Theory Seminar: Efficient quantum algorithms for linear matrix equations and possible applications

Dr. Rolando D. Somma
Google Quantum AI
Theory Seminar, at the Lecture Hall
Monday, July 13, 11:30 CET

I will describe two nearly-optimal quantum algorithms for solving i) linear matrix differential equations and ii) the Sylvester matrix equation. Such equations are fundamental in physics, chemistry, and other areas like control theory. Our approach constructs the solution matrix X as a block-encoding, contrasting approaches that output the solution as a quantum state, which can lead to exponentially-small amplitudes due to normalization. This permits obtaining certain properties of the entries of X exponentially faster. I will mention an end-to-end application: simulating dissipative dynamics for non-interacting fermions, which can also be extended to other systems. I will compare these results with classical algorithms, providing evidence of substantial polynomial quantum speedups for lattice systems, and even better improvements for quantum systems with long-range interactions. I will also comment on a lower bound proving our quantum algorithm is optimal for a large class of instances.