Achieving quantum supremacy would be a scientific breakthrough, not a sign that quantum computers are ready to do useful work. Most of the time when people talk about quantum computing, classical computing is dismissed, like something that is past its prime. But that is not the case, this is an ongoing competition. When it comes to saying where the supremacy threshold is, it depends on how good the best classical algorithms are as they get better, we have to move that boundary. With quantum computers, progress is not just about speed. It’s much more about the intricacy of the algorithms at play.
Ewin’s new algorithm solves the following problem, very loosely stated: given m users and n products, and incomplete data about which users like which products, organized into a convenient binary tree data structure; and given also the assumption that the full m×n preference matrix is lowrank (i.e., that there are not too many ways the users vary in their preferences), sample some products that a given user is likely to want to buy. This is an abstraction of the problem that’s famously faced by Amazon and Netflix, every time they tell you which books or movies you “might enjoy.” What’s striking about Ewin’s algorithm is that it uses only polylogarithmic time: that is, time polynomial in log(m), log(n), the matrix rank, and the inverses of the relevant error parameters. Admittedly, the polynomial involves exponents of 33 and 24: so, not exactly “practical”! But it seems likely to me that the algorithm will run much, much faster in practice than it can be guaranteed to run in theory. Ewin’s algorithm was directly inspired by a quantum algorithm for the same problem, which Kerenidis and Prakash (henceforth KP) gave in 2016, and whose claim to fame was that it, too, ran in polylog(m,n) time. Prior to Ewin’s result, the KP algorithm was arguably the strongest candidate there was for an exponential quantum speedup for a realworld machine learning problem. The new result thus, significantly changes the landscape of quantum machine learning, by killing off one of its flagship applications. To the right is Ewin Tang's mentor Scott Aaronson in his fascinating and entertaining talk, elucidates the potential and the limits of quantum computing. In a sober fashion, he gives an overview of the state of research, telling us not only what we could expect from quantum computers in the future, but also what we probably shouldn't. Scott Aaronson is the David J. Bruton Centennial Professor of Computer Science at The University of Texas at Austin and The director of UT's Quantum Information Center. Before that he taught at MIT for nine years.
Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971. 
I of IV: Race to make quantum computers work
II of IV: what is quantum supremacy?
III of IV: Dr. Gershon explains quantum computing to: a child, teen, a
IV of IV: the potential and the limits of quantum computing.IV of IV: P Vs NP & the computational complexity zoo
He is wellknown for his “complexity zoo,” which helps to
classify problems that can be solved by computers, both quantum and
classical, according to how hard it is to solve them

Science

Technology

Engineering

Mathematics

Empowerment
