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).
By Anthony Leverrier
By Zbigniew Puchała
By Benoit Collins
By Satya Majumdar
By Motohisa Fukuda
By Anand Natarajan
By Nilanjana Datta
By Daniel Stilck Franca
By Ke Li
By Radosław Adamczak
By Madalin Guta
By Antonio Acín
By Ashley Montanaro
By Ping Zhong
By James Mingo
By Camille Male
By Clément Delcamp
By Clément Delcamp
By Claudio Dappiaggi
