IQI Weekly Seminar

Abstract: Over the last few years significant attention has been devoted to devising experimental demonstrations of quantum computational supremacy: namely using a quantum computer to perform a computational task in a regime that goes beyond what is possible on a classical, digital, machine. This is, in part, driven by the hope that a clear demonstration of post-classical computation can be performed with a device that is intermediate between the small quantum circuits that can currently be built and a full-scale, fault-tolerant, quantum computer. The theoretical challenge that this poses is twofold: firstly we must identify the physically least expensive quantum computations that are classically unachievable; and we must also determine if this advantage can be maintained in realistic physical systems. In this talk I will discuss the IQP, Boson Sampling, and chaotic circuit approaches to quantum computational supremacy, how they can be generalized to other intermediate quantum computing models, and to what extent the experimental resource requirements of these problems can be reduced.

This talk is based on joint work with:
[1] M. J. Bremner, A. Montanaro, and D. J. Shepherd, "Achieving quantum supremacy with sparse and noisy commuting quantum computations", Quantum 1, 8 (2017). arXiv:1610.01808
[2] M. J. Bremner, A. Montanaro, and D. J. Shepherd "Average-case complexity versus approximate simulation of commuting quantum computations", Phys. Rev. Lett. 117, 080501 (2016). arXiv:1504.07999
[3] S. Boixo, et al, "Characterizing quantum supremacy in near-term devices", arXiv:1608.00263.
[4] A. Lund, M. J. Bremner, T. C. Ralph "Quantum sampling problems, BosonSampling and quantum supremacy", npj Quantum Information 3, Article number: 15 (2017). arXiv:1702.03061
[5] R. Mann and M. J. Bremner, "On the Complexity of Random Quantum Computations and the Jones Polynomial", arXiv:1711.00686.