Projects per year
Abstract
It is predicted that quantum computers will dramatically outperform their conventional counterparts. However, largescale universal quantum computers are yet to be built. Boson sampling is a rudimentary quantum algorithm tailored to the platform of linear optics, which has sparked interest as a rapid way to demonstrate such quantum supremacy. Photon statistics are governed by intractable matrix functions, which suggests that sampling from the distribution obtained by injecting photons into a linear optical network could be solved more quickly by a photonic experiment than by a classical computer. The apparently low resource requirements for large boson sampling experiments have raised expectations of a nearterm demonstration of quantum supremacy by boson sampling. Here we present classical boson sampling algorithms and theoretical analyses of prospects for scaling boson sampling experiments, showing that nearterm quantum supremacy via boson sampling is unlikely. Our classical algorithm, based on Metropolised independence sampling, allowed the boson sampling problem to be solved for 30 photons with standard computing hardware. Compared to current experiments, a demonstration of quantum supremacy over a successful implementation of these classical methods on a supercomputer would require the number of photons and experimental components to increase by orders of magnitude, while tackling exponentially scaling photon loss.
Original language  English 

Pages (fromto)  11531157 
Number of pages  5 
Journal  Nature Physics 
Volume  13 
Issue number  12 
Early online date  2 Oct 2017 
DOIs  
Publication status  Published  1 Dec 2017 
Structured keywords
 QITG
 Bristol Quantum Information Institute
Fingerprint Dive into the research topics of 'Classical boson sampling algorithms with superior performance to nearterm experiments'. Together they form a unique fingerprint.
Projects

A practical quantum simulator: simulating molecular vibrations with photons. ECF
Engineering and Physical Sciences Research Council
1/11/15 → 30/04/21
Project: Research


Profiles

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

Dr Anthony Laing
 School of Physics  Associate Professor in Physics
 The Bristol Centre for Nanoscience and Quantum Information
 QET Labs
Person: Academic , Member

Professor Ashley M R Montanaro
 School of Mathematics  Professor of Quantum Computation
 The Bristol Centre for Nanoscience and Quantum Information
 Theory and Algorithms
 Mathematical Physics
 Quantum Information Theory
Person: Academic , Member, Group lead