Scientists pinpoint the singularity for quantum computers

October 3, 2017
Dr Anthony Laing, Chris Sparrow and Alex Neville. Credit: University of Bristol

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 before they can beat today's ordinary PCs.

Quantum computers are a new type of machine that operate on mechanical hardware and are predicted to give enormous speed advantages in solving certain problems.

Research groups at leading universities and companies, including Google, Microsoft and IBM, are part of a worldwide race to realise the first quantum computer that crosses into the 'quantum computational singularity'.

This represents a problem so complex that today's top supercomputer would take centuries to find a solution, while a quantum computer could crack it in minutes.

Now a team of scientists from Bristol have discovered that the boundary to this singularity is further away than previously thought.

The research is reported this week in Nature Physics.

The results apply to a highly influential quantum algorithm known as 'boson sampling', which was devised as a very direct route to demonstrate quantum computing's supremacy over classical machines.

The boson sampling problem is designed to be solved by (particles of light) controlled in optical chips – technology pioneered by Bristol's Quantum Engineering and Technology Labs (QETLabs).

Predicting the pattern of many photons emerging from a large optical chip is related to an extremely hard random matrix calculation.

With the rapid progress in quantum technologies, it appeared as though a boson sampling experiment that crossed into the quantum computational singularity was within reach. However, the Bristol team were able to redesign an old classical algorithm to simulate boson sampling, with dramatic consequences.

Dr Anthony Laing, who heads a group in QETLabs and led this research, said: "It's like tuning up an old propeller aeroplane to go faster than an early jet aircraft.

"We're at a moment in history where it is still possible for to outperform the quantum algorithms that we expect to ultimately be supersonic.

"But demonstrating such a feat meant assembling a crack team of scientists, mathematicians, and programmers."

Classical algorithms expert Dr Raphaël Clifford, from Bristol's Department of Computer Science, redesigned several classical algorithms to attack the boson sampling problem, with the 1950's Metropolised Independence Sampling algorithm giving the best performance.

The simulation code was optimised by QETLabs researcher 'EJ', a former LucasArts programmer. Expertise on computational complexity came from Dr Ashley Montanaro, of Bristol's School of Mathematics, while QETLabs students Chris Sparrow and Patrick Birchall worked out the projected performance of the competing quantum photonics technology.

At the heart of the project and bringing all these strands together was QETLabs PhD student and first author on the paper, Alex Neville, who tested, implemented, compared, and analysed, all of the algorithms.

He said: "The largest boson sampling experiment reported so far is for five photons.

"It was believed that 30 or even 20 photons would be enough to demonstrate quantum computational supremacy."

Yet he was able to simulate boson sampling for 20 photons on his own laptop, and increased the simulation size to 30 photons by using departmental servers.

Alex added: "With access to today's most powerful supercomputer, we could simulate boson sampling with 50 photons."

The research builds on Bristol's reputation as a centre of activity for quantum science and the development of quantum technologies.

Through QETLabs, the university has embarked on an ambitious programme to bring quantum technologies out of the laboratory and engineer them in to useful devices that have real-world applications for tackling some of society's toughest problems. 

In addition to collaborations with tech companies such as Microsoft, Google, and Nokia, start-ups and new business activities focused on quantum technologies have emerged in Bristol.

An important theme across the overall quantum research activity is developing our understanding of exactly how quantum technologies can provably outperform conventional computers.

Recently Dr Montanaro, together with Professor Noah Linden of the School of Mathematics, organised a Heilbronn Focused Research Group on the topic of quantum computational supremacy.

This meeting brought some of the world leaders in the field, from both industry and academia, to Bristol for a week of intense discussions and collaboration. Among the attendees was one of the theorists who devised boson sampling, Professor Scott Aaronson, from UT Austin.

Although outperforming classical computers might take a little longer than originally hoped, Dr Laing is still optimistic about the prospects for building a device to do just that.

He said: "We now have a solid idea of the technological challenge we must meet to demonstrate that quantum machines can out-compute their classical counterparts. For boson sampling, the singularity lies just beyond 50 photons. It's a tougher nut to crack than we first thought, but we still fancy our chances."

With Dr Laing's group focused on practical applications of , the current work puts bounds on the size and sophistication of photonic devices that will be required to tackle industrially relevant problems that are beyond the capabilities of today's classical algorithms.

Explore further: The quantum revolution is a step closer

More information: Alex Neville et al. Classical boson sampling algorithms with superior performance to near-term experiments, Nature Physics (2017). DOI: 10.1038/nphys4270

Related Stories

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

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

Spider-web 'labyrinths' may help reduce noise pollution

October 17, 2017

(Phys.org)—Researchers have demonstrated that the geometry of a natural spider web can be used to design new structures that address one of the biggest challenges in sound control: reducing low-frequency noise, which is ...

Plasma optic combines lasers into superbeam

October 17, 2017

Since its introduction in the 1977 film "Star Wars," the Death Star has remained one of science fiction's most iconic figures. The image of Alderaan's destruction at the hands of the Death Star's superlaser is burned into ...

3 comments

Adjust slider to filter visible comments by rank

Display comments: newest first

dobermanmac
not rated yet Oct 03, 2017
While literally true, the above article does an injustice to the speed of a quantum computer. Basically, quantum computers solve QUBOs (quadratic unconstrained binary optimizers). The conceptual hangup in the above article appears to be the need to solve a problem, rather than optimizing an unconstrained one. By the way, ever hear of Rose's law? I feel so sad that people don't understand, but soon we will have AI that does.
Ralph
not rated yet Oct 03, 2017
If quantum computing meets its goals in the coming decades, science will gain a powerful new tool. But difficult mathematical calculations make up only a tiny part of the work performed by today's computers. As far as I can see, most of that work has little to gain from vast increases in speed. Already most of my laptop's considerable (non-quantum!) calculational abilities are going to waste -- despite the fact that I use mathematical software every day.
Da Schneib
not rated yet Oct 03, 2017
Most of the quantum computing algorithms I have seen are narrow of purpose. As a result there is no indication so far that a general-purpose quantum processor would have overall advantages over current very powerful and speedy general-purpose classical processors. In fact there are a large number of tasks at which our current processors will be much more efficient than any quantum processor could ever be.

What we need is programmers who can figure out how to make algorithms for general-purpose computing work on quantum processors. Otherwise, the only use for quantum processors in general computing is as coprocessors, like the math coprocessors we already include in almost all existing general-purpose classical processors. New language features in existing languages would then be added to accomplish the specialized results a quantum coprocessor can provide for specific problems.

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.