Probabilistic techniques for simulating quantum computational supremacy experiments
179 views · Published 6 November 2017 · 46:26 · Indexed 6 November 2026
Channel: Institut Henri Poincaré · 2017 · Science & Technology
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).
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...