One of the goals of quantum information science in the next few years is to use the available quantum technologies to demonstrate a speedup over classical computers for some computational task.
In this talk, I will start by describing the model of quantum computing, the corresponding complexity classes as well as the basic quantum algorithmic techniques.
Then, I will describe some of the recent research activity aiming to achieve a quantum computational advantage with current technologies, focusing on Bravyi, Gosset and Koenig’s paper quantum advantage with shallow circuits and, if time permits, on Bouland, Fefferman, Nirkhe and Vazirani’s paper quantum supremacy and the complexity of random circuit sampling.
References:
- John Watrous’ lecture notes.
- Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. arXiv 1906:08890, June 2019.