Probabilistic techniques for simulating quantum computational supremacy experiments

By Ashley Montanaro (University of Bristol)
Abstract: The fast pace of recent experimental developments has led to the hope that quantum computers will soon demonstrate computational performance far beyond classical computers: a milestone known as quantum (computational) supremacy. However, the relative simplicity of near-term experiments leaves open the possibility that they could be simulated classically more easily than full quantum computers could.
In this talk, I will discuss two such classical simulation results for proposed architectures for quantum computational supremacy experiments. The first is a classical algorithm for simulating certain noisy commuting quantum computations ("IQP circuits") in polynomial time, based on Fourier analysis over Z_2^n. The second is experimental work demonstrating that simple probabilistic methods can be used to simulate boson sampling experiments significantly more efficiently than previously thought. This implies that quantum computational supremacy is unlikely to be achieved via boson sampling in the near future.
The talk is based on joint work with Michael Bremner and Dan Shepherd (Quantum 1, 8 (2017); arXiv:1610.01808), and joint work with Alex Neville, Chris Sparrow, Raphael Clifford, Eric Johnston, Patrick Birchall and Anthony Laing (arXiv:1705.00686).