November 8, 2017 feature

# Hard computing problem might be solvable only by quantum computers

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.

Explore further

**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]

© 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

## User comments

Spaced out EngineerPorgieSpaced out EngineerSo 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?

rrranderantialias_physorgWell done gentlemen...well done.

*slow clap*

physmanidjyithttps://arxiv.org...12.01199

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

*ducks for cover*

knowphiselfderphysThe 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.

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