Scientists pinpoint the singularity for quantum computers

Quantum computers are a new type of machine that operate on quantum 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 photons (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 classical algorithms 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 quantum technologies, 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.