Back in September 2015 I was invited to present a seminar at the Workshop on Quantum Information and Computer Science, hosted by the Joint Centre for Quantum Information and Computer Science at the University of Maryland. (Video above and slides are here.)
My talk was on a recent paper that I wrote together with Ashley Montanaro and Dan Shepherd where we generalized the Boson Sampling argument of Aaronson and Arkhipov to spin systems. We argued that IQP Sampling, the process of sampling from IQP (Instantaneous Quantum Polytime) circuits, can not be efficiently simulated on classical computers to within a constant variation distance assuming a couple of plausible complexity theoretic conjectures.
Why is this interesting? Our argument demonstrates that the dynamics of randomly chosen Ising models can not be classically simulated – so we have identified one of the simplest physical systems that demonstrates so-called quantum supremacy.