4 August 2016

Quantum computers are a new type of computing device that use the principles of quantum mechanics to do things that standard computers cannot do. Large-scale quantum computers are predicted to dramatically outperform current supercomputers for tasks ranging from simulating quantum-mechanical systems to cracking cryptographic codes, and could be used to design new drugs and novel materials.

However, building a quantum computer is hard, and nobody has yet developed a large-scale, general-purpose machine. One of the main reasons for this is the effect of errors. Quantum computers are extremely sensitive to noise from the outside world, and achieving the high level of precision required to combat this is a major technological challenge. Nevertheless, experimental progress has been fast in recent years. Experimental groups worldwide are racing to be the first to reach the major milestone of quantum supremacy: the first demonstration of a quantum computer solving a problem that a supercomputer could not solve in a human lifetime.

In this paper, the researchers propose a family of quantum experiments based on a new approach, known as commuting quantum circuits. This gives an alternative route to quantum supremacy that evades some of the known issues with other approaches. Commuting quantum circuits are a simple class of quantum experiments which can easily be implemented on many types of quantum computer, such as ion traps and superconducting quantum circuits.

Dr Ashley Montanaro, Lecturer in Applied Mathematics and EPSRC Early Career Research Fellow in the School of Mathematics, who carried out the research in collaboration with researchers from CESG and University of Technology Sydney, said: "Achieving quantum supremacy requires finding a problem which is hard for standard computers, yet particularly easy to implement as a quantum experiment. One such proposal is called boson sampling. This is a problem which can easily be solved using linear-optical quantum circuits, an architecture in which Bristol's Centre for Quantum Photonics are world leaders. Although boson sampling is considered likely to be hard to solve on normal computers, this assumption rests on plausible but unproven conjectures, and it is unclear how to implement boson sampling fault-tolerantly.

"We have shown that, if we are willing to assume a natural conjecture in computational complexity theory, commuting quantum circuits cannot be simulated efficiently on a standard computer. This holds even for approximate simulation, and if the quantum computer experiences noise. Unlike boson sampling, commuting quantum circuits can be implemented fault-tolerantly. Our work also highlights intriguing connections between quantum circuits and well-studied concepts from elsewhere in physics and mathematics."

The paper published today in Physical Review Letters is the first step on a new path to quantum supremacy. 

Paper

'Average-case complexity versus approximate simulation of commuting quantum computations' by Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd in Physical Review Letters