Hard computing problem might be solvable only by quantum computers

gaussian boson sampling
The Gaussian state in the computing problem is characterized by a matrix. Credit: Hamilton et al. ©2017 American Physical Society
(Phys.org)—Researchers have introduced a new computing problem and shown that it would be extremely difficult, if not impossible, for a classical computer to solve, but in theory it could be efficiently solved using quantum techniques. The problem, which is called Gaussian boson sampling, is a new version of boson sampling, which is a similar computing problem that was introduced a few years ago with the goal of demonstrating the potential advantages of quantum computers over classical ones.

The researchers of the new study, Craig S. Hamilton et al., from the Czech Technical University in Prague and the University of Paderborn in Germany, have published a paper on Gaussian boson sampling in a recent issue of Physical Review Letters.

Overall, the Gaussian boson sampling problem is very similar to the original boson sampling problem, which was proposed in 2011 by Scott Aaronson and Alex Arkhipov. In both problems, the task is to find the probability of measuring certain patterns of photons emerging from an optical system, given a certain input configuration of photons. In complexity theory, boson sampling is conjectured to be a #P-hard problem, which makes it extremely unlikely that it could be solved by a classical .

Although no quantum computer currently exists that is capable of solving the boson sampling problem, several research groups have attempted to implement and solve the problem using quantum optical experiments. One of the biggest challenges for these experiments is generating a large number of single photons. Since perfectly deterministic sources of are not currently available, all of the experiments performed so far have used photon sources that are probabilistic rather than deterministic.

The downside of using probabilistic photon sources is that the cost of generating the photons scales exponentially as the number of photons increases. So far, the largest number of photons used is five, which is not enough to demonstrate conclusively the advantage of using quantum computers. (Further emphasizing the difficulty of demonstrating a quantum advantage in this area, a recent study has shown that classical computers can simulate the boson sampling problem using 30 photons, suggesting that the quantum methods have more to prove than previously thought.)

In an attempt to make it easier to achieve larger numbers of photons in boson sampling experiments, the researchers in the new study looked specifically at boson sampling using Gaussian states. Although Gaussian states have already been used experiments, their Gaussian nature was never specifically investigated. These states have the advantage of being less costly to produce in experiments.

"The single biggest advantage of our protocol is the ability to use more of the generated photons from our input states," Hamilton told Phys.org. "This means, if number is the main obstacle for experimentalists, it should be easier to demonstrate a quantum advantage using Gaussian states."

One of the main results of the new study is that, despite being easier to implement experimentally, Gaussian boson sampling is still a #P-hard problem and so, like boson sampling, also has the potential to serve as a platform illustrating the advantages of quantum computing. Specifically, the researchers show that Gaussian boson sampling is related to a matrix function called the Hafnian, a problem so difficult that currently no classical computer can efficiently approximate a solution.

Overall, the results suggest that Gaussian boson sampling may have several experimental and theoretical advantages over general sampling, and will likely provide researchers with another tool to investigate where to draw the line between and classical computing.


Explore further

Scientists pinpoint the singularity for quantum computers

More information: Craig S. Hamilton et al. "Gaussian Boson Sampling." Physical Review Letters. DOI: 10.1103/PhysRevLett.119.170501
Also at arXiv:1612.01199 [quant-ph]
Journal information: Physical Review Letters

© 2017 Phys.org

Citation: Hard computing problem might be solvable only by quantum computers (2017, November 8) retrieved 21 May 2019 from https://phys.org/news/2017-11-hard-problem-solvable-quantum.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
767 shares

Feedback to editors

User comments

Nov 08, 2017
But are their such counts if there are tachyon condensates? The fermion already solved it.

Nov 08, 2017
So lets see some evidence of this. I know you only need another $65 or 70 million to prove it or make it work. You are just like fuel cells. Since the mid 70s they have been about 3 years away from commercial operation and their is still no good ones out there 40 years later. Show me something or shut up.

Nov 08, 2017
jd_ it is worse than the traveling salesman, it is counting the number of cycles less than a given certain amount.

So if there is only one electron zipping back and forth through time, does it matter when we ask him? Does all the zig-zag make him miss count? Could he visit with other cousins from variant fracturings of symmetry? As long as he saves two brothers, chances are he will be alright. Of course the DNA of deSitter space might play a little different than just his rind, if the universe were an orange.

Might it matter if we are using many bits with one closed-time like-curve, or one bit with many closed-time like-curves?

Nov 08, 2017
There is a much chance of a working quantum computer in the next 10 years as a tooth fairly popping up and solving equations.

Nov 09, 2017
Wow...you read the comment sections and it's full of people who are either crazy or haven't understood the article one bit.

Well done gentlemen...well done.
*slow clap*

Nov 09, 2017
@rrrander you mean a working quantum computer like this? https://www.theve...ase-date

Nov 09, 2017
If anyone is interested ...
https://arxiv.org...12.01199

Not sure why they believe it's so hard, :-)

*ducks for cover*

Nov 09, 2017
anomalies revisited

Nov 09, 2017
Any simple quantum microscopic system with a sufficient large number of particles (above a few 10 ) is impossible to simulate and calculate on a classical computer, simply because the number of possibilities to calculate is toot huge in a life time even over the age the universe.
The microscopic quantum complexity is dramatically more than the classical complexity.of the macroscopic world.
As explained by Deutsch, any useful quantum computer calculating on many parallel micro-worlds ( 10¨512 with 512 qubits ) will prove the existence of parallel universes to our universe.

Nov 09, 2017
error read 2¨512 with 512 qubits, 2 not 10 or 10¨51 rouhgly !!!!

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more