An optimal LCU-based quantum linear system solver



Université de Paris

October 12, 2022 4:00 PM

In this talk, I will first give an overview of recent techniques such as taking linear combinations of unitaries (LCU) and the quantum singular value transformation framework (QSVT). These techniques allow one to reduce many quantum algorithmic problems to questions about finding good / the best polynomial approximations to certain functions. We study one such function: the inverse. In other words, we consider the problem of solving linear systems of equations. Prior work has shown that an asymptotically optimal approximation to the inverse can be evaluated using LCU and/or QSVT. We show the same for the optimal approximating polynomial, thus achieving constant factor improvements.

This is based on which is joint work with Daniel Szilagyi and Iordanis Kerenidis.

About the speaker
Sander Gribling's research focuses on the interaction between optimization and quantum information theory / quantum computing. He is also interested in the many uses of polynomials in quantum information theory: polynomial optimization, quantum query complexity, and quantum algorithms.

Webpage of the project: