András Gilyén:
Quantum acceleration through linear algebra and
Markov chains
I will explain how quantum computers can use superposition and entanglement to implement large dimensional linear algebra operations in a very efficient, but implicit way by operating on quantum states (whose state space has exponentially large dimension). The efficiency of these linear algebra operations is well understood and can be treated under the unifying umbrella of block-encodings and quantum singular value transformation, leading to applications in linear equation solving, optimization, and the simulation of quantum systems. Further applications relate to, and improve upon randomized algorithms, i.e., Markov Chain Monte Carlo methods.