The goal of the quantum linear systems problem (QLSP) is to prepare a quantum state proportional to the solution of a system of linear equations with a quantum computer. The first quantum algorithm to this end was provided by Harrow, Hassidim, and Lloyd, who also showed that an exponential quantum speedup is indeed possible for this basic linear algebra task. In this talk, I will describe improved quantum algorithms for the QLSP based on recent ideas. One such algorithm improves the complexity dependence of the HHL algorithm exponentially in the precision. The other quantum algorithm is inspired by quantum adiabatic evolutions, is conceptually simple, does not use complex subroutines as other quantum algorithms do, and also improves upon HHL. Last, I will present results on the complexity of quantum state verification that show that verifying the solution to the QLSP is as hard as solving it.
Copyright. All Rights Reserved.