Until roughly a decade ago, the field of quantum computing was developing relatively slowly. There was great (theoretical) promise for the future and a huge experimental effort being driven on many fronts, but useful quantum computers with applications to real-world practical problems still seemed like a distant reality. This motivated the development of the field of quantum computational advantage, centered on more feasible questions: what is the simplest task in which a quantum computer can greatly outperform a classical one? What is the most direct path to test quantum mechanics in the limit of high computational complexity? In other words, what is the easiest way to deliver a demonstration of "raw computational power" of quantum mechanics?

 

In the wake of a demonstration of a photonic quantum device with more than 3000 photons by researchers in China, it seems that the field has matured quickly and quantum computational advantage is now a solid reality. In this talk I will discuss recent advances in this field, and how it is bridging the gap between the hopeful promises of a decade ago and the scalable quantum computers of the future. I will describe the complexity theory arguments underpinning these high-complexity claims as well as important limitations of this paradigm.