By Serge-Paul Carrasco on June 14, 2019

Quantum-inspired Classical Linear Algebra Algorithms

(T) Erwin Tang, last year at the age of 18 rocked the world of quantum-based algorithms, by has given recently a very interesting talk titled “Quantum-inspired classical linear algebra algorithms: why and how?”.

Last year, Erwin proved that ordinary computers can deliver algorithms for recommender systems at the performance potentially comparable to those that can theoretically run on a quantum computer.

Look like from this talk that she is still passionately continuing her journey into the work of quantum-inspired algorithms.

Her talk does not require any particular expertise in quantum computing.

Following is the abstract and the video of her quite interesting talk…

“Abstract: Over the past ten years, the field of quantum machine learning (QML) has produced many polylogarithmic-time procedures for linear algebra routines, assuming certain “state preparation” assumptions. Though such algorithms are formally incomparable with classical computing, a recent line of work uses an analogous classical model of computation as an effective point of comparison to reveal speedups (or lack thereof) gained by QML. The resulting “dequantized” algorithms assume sampling access to input to speed up runtimes to polylogarithmic in input size. In this talk, we will discuss the motivation behind this model and its relation to existing randomized linear algebra literature. Then, we will delve into an example quantum-inspired algorithm: Gilyen, Lloyd, and Tang’s algorithm for low-rank matrix inversion. This dequantizes a variant of Harrow, Hassidim, and Lloyd’s matrix inversion algorithm, a seminal work in QML. Finally, we will consider the implications of this work on exponential speedups in QML.”