Abstract
We study the classical complexity of the exact Boson Sampling problem where the objective is to produce provably correct random samples from a particular quantum mechanical distribution. The computational framework was proposed in STOC ’11 by Aaronson and Arkhipov in 2011 as an attainable demonstration of ‘quantum supremacy’, that is a practical quantum computing experiment able
to produce output at a speed beyond the reach of classical (that is nonquantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation.
Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless P#P = BPPNP and the polynomial hierarchy collapses to the third level.
The fastest known exact classical algorithm for the standard Boson Sampling problem requires O((m+n−1n) n2n) time to produce samples for a system with input size n and m output modes, making it infeasible for anything but the smallest values of n and m. We give an algorithm that is much faster, running in O(n2n + poly(m, n)) time and O(m) additional space. The algorithm is simple to
implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving nearterm quantum supremacy in the context of Boson Sampling.
to produce output at a speed beyond the reach of classical (that is nonquantum) computer hardware. Since its introduction Boson Sampling has been the subject of intense international research in the world of quantum computing. On the face of it, the problem is challenging for classical computation.
Aaronson and Arkhipov show that exact Boson Sampling is not efficiently solvable by a classical computer unless P#P = BPPNP and the polynomial hierarchy collapses to the third level.
The fastest known exact classical algorithm for the standard Boson Sampling problem requires O((m+n−1n) n2n) time to produce samples for a system with input size n and m output modes, making it infeasible for anything but the smallest values of n and m. We give an algorithm that is much faster, running in O(n2n + poly(m, n)) time and O(m) additional space. The algorithm is simple to
implement and has low constant factor overheads. As a consequence our classical algorithm is able to solve the exact Boson Sampling problem for system sizes far beyond current photonic quantum computing experimentation, thereby significantly reducing the likelihood of achieving nearterm quantum supremacy in the context of Boson Sampling.
Original language  English 

Title of host publication  Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA18) 
Editors  Artur Czumaj 
Publisher  Society for Industrial and Applied Mathematics 
Pages  146155 
Number of pages  10 
ISBN (Electronic)  9781611975031 
DOIs  
Publication status  Published  7 Jan 2018 
Fingerprint
Dive into the research topics of 'The classical complexity of Boson sampling'. Together they form a unique fingerprint.Profiles

Dr Raphael Clifford
 School of Computer Science  Reader in Algorithm Design
 Intelligent Systems Laboratory
 Algorithms and Complexity
Person: Academic , Member, Group lead