Hard computing problem might be solvable only by quantum computers

(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 computer.

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 single photons 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 photon 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 boson sampling, and will likely provide researchers with another tool to investigate where to draw the line between quantum and classical computing.

© 2017 Phys.org