Qalgo 10: The HHL algorithm

In this video we go over the quantum algorithm by Harrow, Hassidim, and Lloyd (HHL) for producing a quantum state that encodes the solution to a system of linear equations. We discuss the key ingredients that go into the algorithm, including Hamiltonian simulation, phase estimation, and amplitude amplification, and give a high-level overview of how the algorithm works.

We then analyze the running time and discuss the conditions needed for the algorithm to be efficient. These conditions have made it difficult to find killer applications of HHL and we discuss this as well.

Finally we briefly mention the area of quantum-inspired classical algorithms that resulted from looking at an apples to apples comparison of classical algorithms and HHL.