High-dimensional linear algebra in quantum algorithms: from quantum walks to matrix inversion
High dimensional linear algebra operations can be very efficiently performed on a quantum computer in some cases. In recent years significant effort has been devoted to understanding when such tools can be efficiently employed. In a way many of these algorithms can be understood as a generalization of certain quantum walk algorithms through the lenses of quantum singular value transformation. In the talk I will explain how quantum walks work, and show some examples where they provide non-trivial speed-ups that for some highly structured graphs can yield up to an exponential advantage. Then I will show how quantum walks generalize to quantum singular value transformation, and explain the HHL algorithm for solving certain large systems of linear equations as an interesting application of these techniques.