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