Quantum computing comes a step closer

A new way to run a quantum algorithm using much simpler methods than previously thought has been discovered by a team of researchers at the University of Bristol, according to a university press release. These findings could dramatically bring forward the development of a ‘quantum computer’ capable of beating a conventional computer.

Theories show how computing devices that operate according to quantum mechanics can solve problems that conventional computers, including super computers, can never solve. These theories have been experimentally tested for small-scale quantum systems, but the world is waiting for the first definitive demonstration of a quantum device that beats a classical computer.

Now, researchers from Bristol University’s Centre for Quantum Photonics (CQP), together with colleagues from the University of Queensland (UQ) and Imperial College London have increased the likelihood of such a demonstration in the near term by discovering a new way to run a quantum algorithm with much simpler methods than previously thought.

The first definitive defeat for a classical computer could be achieved with a quantum device that runs an algorithm known as Boson Sampling, recently developed by researchers at MIT (PDF).

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.

Unlike other quantum algorithms, Boson Sampling has the benefit of being practical for near-term implementations, with the only experimental drawback being the difficulty of generating the dozens of single photons required for the important quantum victory.

However, the Bristol-UQ-Imperial researchers have found that the Boson Sampling algorithm can still be proven to be hard for classical computers when using standard probabilistic methods to generate single photons.

Dr Anthony Laing, who led the CQP elements of the research, said: “We realised 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.”

The research was published last week in Physical Review Letters under the title ‘Boson Sampling from a Gaussian State‘.