How a quantum computer could defeat a classical computer

September 16, 2014

Schematic of a boson-sampling device (credit: A. P. Lund et al./PRL)

The first definitive defeat for a classical computer by a quantum computer could one day be achieved with a quantum device that runs an algorithm known as “boson sampling,” recently developed by researchers at MIT.

Boson sampling uses single photons of light and optical circuits to take samples from an exponentially large probability distribution, which has been proven to be extremely difficult for classical computers.

The snag: how to generate the dozens of single photons needed to run the algorithm.

Now researchers at the Centre for Quantum Photonics (CQP) at the University of Bristol with collaborators from the University of Queensland (UQ) and Imperial College London say they have discovered how.

“We realized we could chain together many standard two-photon sources in such a way as to give a dramatic boost to the number of photons generated,” said CQP research leader Anthony Laing, a research fellow at the Centre for Quantum Photonics in the University of Bristol’s School of Physics.

Details of the research are in a paper published in Physical Review Letters.

Sources of single photons

First author Austin Lund of the Centre for Quantum Computation and Communication Technology, School of Mathematics and Physics, University of Queensland, explained to KurzweilAI that “we have shown that a variant of the boson-sampling problem can be realized using sources of photons from spontaneous parametric down conversion (SPDC).

Spontaneous parametric down-conversion is the most readily accessible source of single photons (the multiplexer can also be eliminated) (credit: Peter Rhode)

“These are sources of photons which can be thought of as distinguishable pairs of photons. Usually experiments will measure one of these photons which then heralds the presence of the partner photon.

“Though this can be a good source of high quality photons, unfortunately, it is necessarily probabilistic with the probability dropping exponentially in the number of photons desired.

“We have shown that this exponential drop in probability does not matter for the case of Boson Sampling. We have shown that SPDC style resources can be used to prove that a slightly modified version of Boson Sampling is hard for a classical computer to calculate.

“Since the original Boson Sampling algorithm study in 2010 there has been great interest in the quantum computing community to understand what particular aspect of quantum mechanics enhances the computing power for this particular algorithm.

“There has also been interest in the quantum optics community due to the simple nature of this algorithm for implementing the required interactions between photons. Indeed very small scale implementations of boson sampling have been achieved. Our result adds to this work by potentially allowing a simpler path to a large scale implementation which may challenge the limits of classical computers simulating this problem.”

Time frame: five to 20 years

So when might this happen? Lund told KurzweilAI that their focus has been on “pushing the boundaries of science and to what can be achieved. It is always difficult to give reasonable estimates on time frames as they generally depend on factors largely outside the control of scientists. Though we have seen demonstrations of pretty much all the bits and pieces needed to produce a device that outperforms a classical computer.

“The major challenge is in achieving the scale required, i.e., dozens of photons into hundreds of paths. There are people ready to take on this challenge awaiting the resources needed. If that happens soon, then in 5 years we may see the first quantum computing device which has a provable speed up over a classical computer. Perhaps a more likely time frame is 20 years. I’m keen to be surprised on this though.”

The research was supported by the Australian Research Council Centre of Excellence for Quantum Computation and Communication Technology, the Army Research Office (ARO), the Engineering and Physical Sciences Research Council (EPSRC), the European Research Council (ERC), the Centre for Nanoscience and Quantum Information (NSQI), the U.S. Air Force Office of Scientific Research (AFOSR) and the U.S. Army Research Laboratory (ARL).


Peter Rohde | A brief introduction to the exciting new field of boson-sampling optical quantum computing.


Abstract of Physical Review Letters paper

We pose a randomized boson-sampling problem. Strong evidence exists that such a problem becomes intractable on a classical computer as a function of the number of bosons. We describe a quantum optical processor that can solve this problem efficiently based on a Gaussian input state, a linear optical network, and nonadaptive photon counting measurements. All the elements required to build such a processor currently exist. The demonstration of such a device would provide empirical evidence that quantum computers can, indeed, outperform classical computers and could lead to applications.