Hard computing problem might be solvable only by quantum computers

November 8, 2017 by Lisa Zyga, Phys.org feature
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]

Related Stories

Scientists pinpoint the singularity for quantum computers

October 3, 2017

Researchers from the University of Bristol have discovered that super-powerful quantum computers, which scientists and engineers across the world are racing to build, need to be even more powerful than previously thought ...

The quantum revolution is a step closer

September 11, 2014

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. These findings could dramatically bring forward the development ...

Photonic quantum computers: A brighter future than ever

May 13, 2013

(Phys.org) —Harnessing the unique features of the quantum world promises a dramatic speed-up in information processing as compared to the fastest classical machines. Scientists from the Group of Philip Walther from the ...

A new kind of quantum computer

November 6, 2017

Quantum mechanics incorporates some very non-intuitive properties of matter. Quantum superposition, for example, allows an atom to be simultaneously in two different states with its spin axis pointed both up and down, or ...

Verifying the future of quantum computing

July 30, 2014

Physicists are one step closer to proving the reliability of a quantum computer – a machine which promises to revolutionise the way we trade over the internet and provide new tools to perform powerful simulations.

Recommended for you

How community structure affects the resilience of a network

June 22, 2018

Network theory is a method for analyzing the connections between nodes in a system. One of the most compelling aspects of network theory is that discoveries related to one field, such as cellular biology, can be abstracted ...

The pho­to­elec­tric ef­fect in stereo

June 22, 2018

In the photoelectric effect, a photon ejects an electron from a material. Researchers at ETH have now used attosecond laser pulses to measure the time evolution of this effect in molecules. From their results they can deduce ...

Water can be very dead, electrically speaking

June 21, 2018

In a study published in Science this week, the researchers describe the dielectric properties of water that is only a few molecules thick. Such water was previously predicted to exhibit a reduced electric response but it ...


Adjust slider to filter visible comments by rank

Display comments: newest first

Spaced out Engineer
1 / 5 (2) Nov 08, 2017
But are their such counts if there are tachyon condensates? The fermion already solved it.
1 / 5 (2) 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.
Spaced out Engineer
1 / 5 (2) 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?
1.5 / 5 (2) 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.
5 / 5 (1) 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*
5 / 5 (1) Nov 09, 2017
@rrrander you mean a working quantum computer like this? https://www.theve...ase-date
2.3 / 5 (3) Nov 09, 2017
If anyone is interested ...

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

*ducks for cover*
1 / 5 (1) Nov 09, 2017
anomalies revisited
1 / 5 (1) 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.
1 / 5 (1) 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

Click here to reset your password.
Sign in to get notified via email when new comments are made.