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 computer.
Read more at: https://phys.org/news/2017-11-hard-problem-solvable-quantum.html#jCp
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 computer.